그래프 탐색
-
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문을 이용해 벽을 세울 수 있는 모든..
-
Q. 3184 자바 : 양코딩테스트/백준_Java 2023. 4. 2. 01:07
Q. 3184 자바 : 양 문제 : boj.kr/3184 실버 1 난이도의 문제이다. 격자형 그래프에 양, 늑대, 울타리가 주어지고, 울타리 내에 양과 늑대의 수를 비교해서, 양이 더 많을경우 늑대를 없애고 늑대와 양의 수가 같거나 늑대가 많을 경우 양을 없앤다. 이후 모든 울타리에 생존한 양과 늑대에 수를 출력하는 문제이다. 생각해야 되는 입력값이 빈 필드, 양, 늑대, 울타리이고, 이걸 어떻게 탐색을 하면 될까 고민해서 아래와 같은 방식으로 풀었다. 1. 처음 시작할 때는 양이나 늑대일 경우 탐색을 시작한다. (모든 탐색 여부는 visit[][] 배열에 표시) 2. 이후 다른 영역을 탐색할 때는 울타리가 아닌 경우 무조건 탐색을 한다. 3. 위 탐색이 한 번 끝나면 양과 늑대의 수를 비교해 조건에 따..
-
Q. 4963 자바 : 섬의 개수코딩테스트/백준_Java 2023. 4. 1. 09:51
Q. 4963 자바 : 섬의 개수 문제 : boj.kr/4963 실버 2 난이도의 문제이다. 격자 그래프가 주어졌을 때 이를 DFS, BFS로 순회하고 결과를 출력하는 문제이다. 주의해야 할 점은 순회 방향이 상 하 좌 우 + 대각선을 포함한다 그래서 탐색을 위한 dy, dx의 크기를 8로 늘리고 대각선 4방향을 추가해줬다. 그래프의 크기 W, H가 중지므로 시간복잡도는 아래와 같다. 1. DFS or BFS 순회 - O(W * H) 이 때 W, H의 최대값은 50이므로 시간초과는 걱정하지 않아도 된다. 그래프의 자료형은 boolean 2차원 배열로 해결했다. 풀이는 아래와 같다. import java.io.*; import java.lang.reflect.Array; import java.util.*;..
-
Q. 1012 자바 : 유기농 배추코딩테스트/백준_Java 2023. 3. 30. 22:49
Q. 1012 자바 : 유기농 배추 문제 : bo.kr/1012 실버 2 난이도의 문제이다. 이전 글에서 푼 문제인 단지번호 붙이기와 거의 비슷한 문제이다. 배추를 재배하는 땅들의 좌표가 주어진다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 될 때, 총 몇 마리의 지렁이가 필요한지 계산하는 문제이다. 지도의 크기 M, N이 주어지는데, 격자형 그래프 순회 문제의 경우 모든 점을 순회해야 하므로 시간 복잡도는 O(NM)이고, 문제에서N, M의 최대값은 각각 50이므로시간초과는 걱정하지 않아도 된다. 또한 입력을 받을 때 자료형은 0과 1로만 구분되므로 boolean을 사용했다. 문제를 푼 방식은 1. 탐색이 가능한 경우(arr[y][x] = true) 방문하고, 이후에 탐색을 진행하며 방문 ..
-
Q. 2667 자바 : 단지번호붙이기코딩테스트/백준_Java 2023. 3. 29. 13:35
Q. 2667 자바 : 단지번호붙이기 문제 : boj.kr/2667 실버 1 난이도의 문제이다. 0과 1로 구성된 격자형 그래프가 주어지고, 1(=집을 의미)이 모여 있는 곳을 단지로 정의했을 때, 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제이다. 지도의 크기 N이 주어지는데, 격자형 그래프 순회 문제의 경우 모든 점을 순회해야 하므로 시간 복잡도는 O(N^2)이고,문제에서N의 최대값은 25이므로 시간초과는 걱정하지 않아도 된다. 또한 입력을 받을 때 자료형은 0과 1로만 구분되므로 boolean을 사용했다. 문제를 푼 방식은 1. 탐색이 가능한 경우(arr[y][x] = true) 방문하고, 이후에 탐색을 진행하며 방문 횟수를 저장한다. (이 때 방문한 경우 방문..
-
Q. 1260 자바 : DFS와 BFS코딩테스트/백준_Java 2023. 3. 28. 12:02
Q. 1260 자바 : DFS와 BFS 문제 :boj.kr/1260 실버 2 난이도의 문제이다. 그래프가 주어졌을 때 이를 DFS, BFS로 순회하고 결과를 출력하는 문제이다. 주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 한다는 내용 때문에 그래프를 입력 받은 뒤 정렬이 한번 필요하다. 정점이 N, 간선이 M으로 주어지므로 시간복잡도는 아래와 같다. 1. 모든 정점에 대한 정렬 - O(N * M log M) 2. DFS, BFS 순회 - O(2 * N * M) (ArrayList를 이용한 그래프 탐색의 경우 정점 * 간선 만큼의 시간복잡도를 가짐) 따라서 두 식을 더하면 약 O(N * M) 정도의 시간복잡도를 가진다고 예상할 수 있다. 이 문제의 경우 정..