연결된 그룹 개수 찾기(DFS)

1. 각 노드의 방문 여부를 체크할 배열 생성
2. 각 노드에 연결된 노드를 추가할 배열 리스트를 추가
3. 각 노드에 연결된 노드들을 찾아 각 노드의 배열 리스트에 추가
4. 방문하지 않은 노드일 경우, dfs 진행 및 count 1 증가
dfs
- 1. 방문할 노드인 경우 즉시 탈출,
- 2. 해당 노드를 방문한 걸로 바꾸기
- 3. 연결된 노드들을 순회하면서 방문하지 않은 노드가 있다면, dfs 진행

 

class Solution {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;

    public int solution(int n, int[][] computers) {
        // 1
        visited = new boolean[n];
        // 2
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        // 3
        for (int i = 0; i < computers.length; i++) {
            for (int j = 0; j < computers[i].length; j++) {
                int from = i;
                int to = j;
                if (computers[i][j] == 1) {
                    graph.get(from).add(to);
                    graph.get(to).add(from);
                }
            }
        }
        // 4
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i);
                count++;
            }
        }
        return count;
    }

    // 5
    private void dfs(int node) {
        if (visited[node]) return;
        visited[node] = true;
        int size = graph.get(node).size();
        for (int i = 0; i < size; i++) {
            int value = graph.get(node).get(i);
            if (!visited[value]) {
                dfs(value);
            }
        }
    }
}