Today's Algorithm(2018-11-19)

programmers 네트워크

깊이/너비 우선 탐색으로 풀 수 있는 문제 중 가장 간단한 형태의 문제 중 하나가 아닐까 생각합니다. 한마디로 연결되어 있는 네트워크의 개수를 구하라는 것이죠. 모두가 이어져 있으면 1개, 만약 모두 연결되어 있지 않으면 n이 반환되는 것입니다. 이 경우 '깊이 우선 탐색', '너비 우선 탐색' 모두 사용 가능한데요. 저는 Queue를 이용한 '너비 우선 탐색'을 이용하였습니다. 대략적인 풀이 방법은 다음과 같습니다.

 

1. n개의 반복문을 돌면서 방문하지 않은 컴퓨터를 하나 고릅니다.
2. 방문하지 않은 컴퓨터를 큐에 넣고 방문 표시 및 네트워크 개수를 +1 증감합니다.
3. 이 큐가 비워질 때까지 반복합니다. 그 반복문 안에서 우선 큐 안의 값을 하나 꺼낸다음 그 값(컴퓨터)에 연결된 값들을 탐색합니다. 그 중 아직 방문하지 않았고 해당 값과 연결된 컴퓨터를 큐 안에 넣습니다.

 

3번이 제일 핵심입니다. 이 과정에서 연결된 컴퓨터들을 모조리 방문 체크가 되기 때문에 제일 상위 반복문에서는 기존에 방문하지 않은 컴퓨터들 중에서 추가적으로 탐색이 가능한 것입니다. 이 과정을 코드로 정리하면 다음과 같습니다.

class Solution {
    public int solution(int n, int[][] computers) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[n];
        int answer = 0;

        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                queue.offer(i);
                visit[i] = true;
                answer++;

                bfs(computers, queue, visit);
            }
        }
        return answer;
    }

    private void bfs(int[][] computers, Queue<Integer> queue, boolean[] visit) {
        while (!queue.isEmpty()) {
            int num = queue.poll();
            for (int j = 0; j < computers[num].length; j++) {
                if (computers[num][j] == 1 && visit[j] == false) {
                    queue.offer(j);
                    visit[j] = true;
                }
            }
        }
    }
}