그래프 탐색
-
Q. 5567 자바 : 결혼식코딩테스트/백준_Java 2023. 4. 12. 09:23
Q. 5567 자바 : 결혼식 문제 : boj.kr/5567 실버 2 난이도의 문제이다. 간선이 주어지고 탐색을 통해 깊이가 2인 정점까지 방문 가능하다면 몇 개의 정점을 방문 가능한지 세는 문제이다. (상근이의 친구 - 깊이가 1, 친구의 친구 - 깊이가 2) 간선만 주어지므로 격자형 그래프가 아니라 ArrayList를 사용해서 문제를 해결했다. 또한 양방향 그래프이므로 간선을 입력받을 때 두 정점 모두 표시했다. 이 문제의 경우 아래와 같은 방식으로 해결했다. 1. 입력값을 받아 두 정점에 저장한다. 2. 깊이우선탐색(DFS)를 시작한다. 3. 이 때 주의해야 할 점은 깊이가 2일 때 까지 모든 정점을 탐색해야 하므로 방문 여부 확인은 하되, 이미 방문한 정점에 대해서도 탐색한다. (어떤 사람에게는 ..
-
Q. 18404 자바 : 현명한 나이트코딩테스트/백준_Java 2023. 4. 11. 09:21
Q. 18404 자바 : 현명한 나이트 문제 : boj.kr/18404 실버 1 난이도의 문제이다. 앞의 나이트의 이동 문제와 비슷하다. 나이트의 위치가 주어지고, 잡아야 할 말의 위치가 여러 개 주어진다. 이 때 각각의 말을 나이트가 몇 번 움직여서 말을 잡을수 있는지 출력하는 문제이다. 격자형 그래프 탐색문제에서 상 하 좌 우 순회하는 방식을 응용해탐색하는 범위만 바꾸면 쉽게 풀리는 문제이다. 체스판의 한 변의 길이로 주어지는 N의 최대값이 500이고, 잡아야 할 말의 수 M의 최대값이 1000이다. 따라서 시간복잡도는 아래와 같다. 1. 주어진 말의 수 - O(M) 2. BFS 순회 - O(N ^ 2) 시간복잡도는 약 O(N ^ 2)이고, 최대 2500000번 계산을 하면 문제를 해결할 수 있다. ..
-
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..