import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
int twin = sc.nextInt();
int[][] graph = new int[size + 1][size + 1];
int[] check = new int[size + 1];
Map<Integer, List<Integer>> map = new HashMap<>();
// 그래프 형성
for (int i = 0; i < twin; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph[a][b] = graph[b][a] = 1;
}
// map에다가 해당하는 노드 연결
for (int i = 1; i <= size; i++) {
List<Integer> tmp = new ArrayList<>();
for (int j = 1; j <= size; j++) {
if (graph[i][j] == 1) {
tmp.add(j);
}
}
map.put(i, tmp);
}
int count = dfs(map, check, 1, 0);
System.out.println(count);
}
public static int dfs(Map<Integer, List<Integer>> map, int[] check, int node, int count) {
check[node] = 1;
for (int i : map.get(node)) {
if (check[i] == 0) {
count = dfs(map, check, i, count+1);
}
}
return count;
}
}
이 문제는 DFS/BFS 및 그래프 문제를 풀어보기 위해 찾아서 푼 문제이다. 난생 처음으로 꽤나 어려운 문제를 풀어보기로 하고 풀었는데, 생각보다 쉽게 풀리다 막판가서 DFS구현에서 막혔다. 풀이는 이러하다.
문제 자체가 무방향 그래프를 제시해줌으로써, graph[a][b] = graph[b][a] = 1
이라는 것을 캐치했다.
문제를 보면 방향성이 없기 때문에, 각 노드가 서로 연결되어있다고 보는 것이다. 이차원배열을 통해 graph
를 구현하고, 이를 Map
에다가 결과값을 담았다. Map
은 Map<Integer, List<Integer>>
이다. 키는 각 노드를 의미하고, 밸류는 각 노드와 연결되어 있는 지점을 의미한다.
그렇게 map을 만들고나서 어떻게 구현하지 하다가 DFS가 떠올라서 DFS로 풀었다.
문제가 1번 컴퓨터에 바이러스가 발생했을 시, 몇 대의 컴퓨터가 동시에 바이러스가 발생하는지 찾는 것이기 때문에 각 노드들의 연결된 고리를 다 찾고 들어가야하기 때문에 DFS를 사용했다.
[출처] : 개인저장소