깊이/너비 우선 탐색(DFS/BFS)- 네트워크

이 문제는 각 컴퓨터를 그래프의 노드로 보고, 연결된 컴퓨터 사이에 엣지를 둔다면, 네트워크의 개수를 찾는 것은 그래프에서 연결된 컴포넌트의 수를 세는 것과 같다. 그래서 이 문제는 DFS(깊이 우선 탐색)에 알아야 한다.

class Solution {
    public int solution(int n, int[][] computers) {
        boolean[] visited = new boolean[n];
        int networkCount = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, visited, computers);
                networkCount++;
            }
        }

        return networkCount;
    }

    private void dfs(int node, boolean[] visited, int[][] computers) {
        visited[node] = true;

        for (int i = 0; i < computers.length; i++) {
            if (computers[node][i] == 1 && !visited[i]) {
                dfs(i, visited, computers);
            }
        }
    }
}

 

문제 풀이

1. visited 배열을 사용하여 각 컴퓨터의 방문 여부를 알아야한다.

2. 모든 컴퓨터를 순회하면서 방문하지 않은 컴퓨터를 발견할 때마다 DFS를 호출하여 해당 네트워크를 완전 탐색한다.

3. 네트워크가 새로 발견될 때마다 'networkCount' ㄹ를 증가해준다.

4. 현재 노드를 방문 처리하고, 해당 노드와 연결된 다른 노드들 중 방문하지 않은 노드를 탐색해야한다.

 

 

Script

---

이 문제는 DFS, BFS 를 알아야한다. 그리고 시간 복잡도가 얼마나 걸리는지도 알아야한다. DFS와 BFS가 무엇이고 시간 복잡도가 얼마나 걸리는 건지 공부 후 정리 한번 해야겠다.