분류 전체보기
-
Q. 7562 자바 : 나이트의 이동코딩테스트/백준_Java 2023. 4. 10. 09:02
Q. 7562 자바 : 나이트의 이동 문제 : boj.kr/7562 실버 1 난이도의 문제이다. 나이트의 위치가 주어지고, 잡아야 할 말의 위치가 주어진다. 이 때 나이트가 몇 번 움직여서 말을 잡을수 있는지 출력하는 문제이다. 격자형 그래프 탐색문제에서 상 하 좌 우 순회하는 방식을 응용해 탐색하는 범위만 바꾸면 쉽게 풀리는 문제이다. 체스판의 한 변의 길이로 주어지는 I의 최대값이 300이므로 시간복잡도는 1. BFS 순회 - O(I ^ 2) 한번으로 최대 90000번 계산을 하면 문제를 해결할 수 있다. 따라서 시간초과는 걱정하지 않아도 된다. 또한 자료형 역시 int 범위 내에서 모두 해결할 수 있다. 풀이는 아래와 같다. import java.io.*; import java.util.*; pub..
-
Q. 3055 자바 : 탈출코딩테스트/백준_Java 2023. 4. 9. 13:27
Q. 3055 자바 : 탈출 문제 : boj.kr/3055 골드 4 난이도의 문제이다. 격자형 그래프가 주어지고, 비어있는 곳은 '.', 물이 차있는 지역은 '*', 돌은 'X', 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 주어질 때 S가 D로 갈 수 있는 최단경로를 계산하는 문제이다. 주의해야 할 점은 물이 차있는 지역인 *는 비어있는 곳 '.'로 확산되고, 물이 차있는 지역은 고슴도치가 갈 수 없다는 점 이다. 어떻게 풀지 고민을 해봤더니, 먼저 물이 차있는 곳에 대해 BFS를 하고 이후에 고슴도치가 BFS를 하면 풀 수 있을 것 같아 이렇게 풀었다. 1. 물이 차있는 곳을 큐에 넣는다. 2. 고슴도치의 위치는 저장했다가, 물이 차있는 곳이 모두 큐에 들어가면 이후에 큐에 넣는다. 3. 탐색을..
-
Q. 1697 자바 : 숨바꼭질코딩테스트/백준_Java 2023. 4. 8. 13:16
Q. 1697 자바 : 숨바꼭질 문제 : boj.kr/1697 실버 1 난이도의 문제이다. 두 점 N, K가 주어지고, N이 이동할 수 있는 방식은 총 3개이며 각각 1초가 소요된다면(N + 1, N - 1, N * 2)N이 K로 갈 수 있는 가장 빠른 시간을 구하는 문제이다. 만약 그래프 탐색 관련 문제를 풀고 있지 않았다면처음 이 문제를 봤을 때 그래프 탐색 문제라고 생각하지 못했을 것 같다.고민해보니 세가지 이동방식에 대한 BFS를 이용하면 풀 수 있을 것 같아 이 방식을 이용해서 풀었다. 1. 정점 N에서 이동 가능한 세 가지 방식에 따른 좌표를 큐에 넣는다.2. 만약 방문했다면 재방문하지 않는다.(가장 먼저 방문한 경우가 가장 빠른 경우이므로 재방문했다면 더 빨라질 수는 없다.) 시간복잡도를 계..
-
Q. 2178 자바 : 미로 탐색코딩테스트/백준_Java 2023. 4. 7. 09:06
Q. 2178 자바 : 미로 탐색 문제 : boj.kr/2178 실버 1 난이도의 문제이다. 격자형 그래프의 크기 N, M과 그래프가 주어졌을 때 1,1부터 N,M까지 갈 수 있는 최소 이동 횟수를 출력하는 문제이다. 주의해야 할 점은 시작점인 1, 1과 도착점인 N, M도 이동 횟수에 포함된다는 점 이다. 최악의 경우는 아래와 같은 경우이며 111111111 100000000 111111111 100000000 111111111 100000000 111111111 이 경우 시간복잡도는 약 O(NM)이다. 이 문제의 경우 N과 M의 최대값이 100이므로 시간초과는 걱정하지 않아도 된다. 또한 도착위치로 이동할 수 없는 경우는 주어지지 않는다고 했으므로 고려하지 않아도 되고, 이동 가능한 칸과 이동이 불가..
-
Q. 11725 자바 : 트리의 부모 찾기코딩테스트/백준_Java 2023. 4. 6. 09:48
Q. 11725 자바 : 트리의 부모 찾기 문제 : boj.kr/11725 실버 2 난이도의 문제이다. 정점의 개수와 간선이 주어졌을 때(방향성x) 만약 1번 정점이 루트라면 2번 정점부터 부모 노드의 번호를 출력하는 문제이다. 처음 이 문제를 봤을 때는 좀 막막했다. 만약 그래프 탐색 문제인줄 모르고 봤다면 문제를 푸는데 시간이 더 오래 걸렸을 것 같다. 고민을 좀 해보니, 간선이 다 주어지므로 모든 간선을 입력받은 뒤에루트가 1이므로 1부터 탐색을 해 가면서 방문 여부를 확인하면 될 것 같다는 생각이 들었다. 그래서 아래와 같은 방식으로 풀었다.1. 입력된 모든 간선은 양방향 그래프이므로, 모두 연결한다.2. 1번 정점부터 탐색을 하면서, 어떤 정점에서 호출 됬는지(부모)를 저장한다. 시간 복잡도는 ..
-
Q. 11403 자바 : 경로 찾기코딩테스트/백준_Java 2023. 4. 5. 09:31
Q. 11403 자바 : 경로 찾기 문제 : boj.kr/11403 실버 1 난이도의 문제이다. 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로 존재 여부를 구하라는 내용이다. 그래프 탐색 강의를 듣고 예제 문제를 푸는 도중이었는데 이 문제는 List를 그래프 탐색이라고 되어 있어서 List를 사용해서 풀었지만, 만약 이를 몰랐다면 입력이 격자형 그래프로 주어져서 격자형 그래프로 풀었을 것 같다. 문제를 이해하는데 시간이 좀 걸렸다.. 입력이 아래와 같이 주어졌을 때 3 0 1 0 0 0 1 1 0 0 출력이 아래와 같다. 1 1 1 1 1 1 1 1 1 즉 정점이 0, 1, 2가 있다면 입력을 간선으로 바꾸면 0 -> 1, 1 -> 2, 2 -> 0..
-
Q. 2606 바이러스코딩테스트/백준_Java 2023. 4. 4. 09:04
Q. 2606 바이러스 문제 : boj.kr/2606 실버 3 난이도의 문제이다. 컴퓨터의 수와 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어지고 이후에 연결된 컴퓨터 쌍이 주어진다 이 때 1번 컴퓨터가 바이러스에 걸렸다면, 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 계산하는 문제이다. 이를 그래프로 설명하자면 양방향 그래프가 주어지고 정점과 간선의 수 그리고 간선이 주어진다. 이 때 1번 정점에 연결된 다른 정점의 수를 계산하는 문제이다. 그래프와 연결된 간선을 List로 구현한 뒤 dfs, bfs 두 방식으로 풀었다 List를 이용한 그래프 탐색의 경우 정점을 V, 간선을 E라고 하면 시간복잡도가 O(V + E)이고 문제 조건에서 정점이 최대 100개이므로 이 경우 간선이 ..
-
Q. 14502 연구소코딩테스트/백준_Java 2023. 4. 3. 12:20
Q. 14502 연구소 문제 : boj.kr/14502 골드 4 난이도의 문제이다. 바이러스(2) 벽(1) 빈 공간(0)을 의미하는 격자형 그래프가 주어지고, 바이러스는 빈 공간이 있으면 확산된다는 조건이 있다. 이 때 벽을 세 개 세워서 바이러스의 확산을 최대한 막는 방법을 물어보는 문제이다. 처음 문제를 봤을 때 든 생각은 벽을 세울 수 있는 모든 경우의 수를 dfs로 구현한 뒤 벽을 3개 만들었을 경우, 바이러스를 확산시켜 빈 공간의 수를 계산하는 방식을 떠올렸다. 근데 막상 구현을 하다 보니 너무 복잡해지는 것 같아 생각을 바꿨다. 아래와 같은 방식으로 구현을 했다. 1. 빈 공간(0)을 리스트에 모두 저장한다. 2. 벽을 최대 3개 세울 수 있으므로 3중for문을 이용해 벽을 세울 수 있는 모든..