[알고리즘 - graph] 네트워크

문제 이해

문제 링크

문제에 int[][]computers 배열로 컴퓨터의 연결에 대한 정보가 주어진다. 서로 연결된 컴퓨터들은 하나의 네트워크를 이룬다고 할 때 총 네트워크의 개수를 구하는 문제이다.

예를 들어 연결이 아래와 같다면 네트워크는 2개이고

아래와 같다면 네트워크는 1개가 된다.

풀이

이 문제는 전형적인 그래프 탐색 문제로, visited 배열에 방문한 노드들을 저장하면서 노드를 탐색해나가는데, 새로운 네트워크가 발견될 때마다 해당 네트워크에 연결된 모든 노드를 탐색 상태로 만들어둔다. 이렇게 하면 아직 탐색되지 않은 노드가 발견된다는 의미가 새로운 네트워크를 발견한다는 의미와 같아지므로 그때마다 count를 증가시켜서 총 네트워크의 개수를 확인할 수 있다.

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]) {
            continue;
        }
        networkCount++;
        visitAllComputersInNetwork(computers, visited, i);
    }

    return networkCount;
}

먼저 위 코드를 통해 visited 배열을 만들고, 전체 노드 (0 ~ n) 을 순회하며 현재 노드가 아직 방문되지 않았을 경우에만 해당 노드가 속한 네트워크의 모든 노드를 visitAllComputersInNetwork() 메서드를 통해 탐색한다.

public void visitAllComputersInNetwork(final int[][] computers, boolean[] visited, int startIndex) {
    Stack<Integer> stack = new Stack<>();
    stack.push(startIndex);

    while(!stack.isEmpty()) {
        int currentIndex = stack.pop();
        visited[currentIndex] = true;

        // 인접 노드 stack에 추가
        for (int i = 0 ; i < computers[currentIndex].length ; i++) {
            if (!visited[i] && !stack.contains(i) && computers[currentIndex][i] == 1) {
                stack.push(i);   
            }
        }
    }
}

visitAllComputersInNetwork() 메서드는 Stack을 이용해서 DFS로 노드들을 탐색한다. 탐색하면서 현재 노드는 탐색 완료 상태로 만들고, 새롭게 탐색한 노드(컴퓨터)에 인접한(연결된) 노드가 있다면 Stack에 추가해서 한번 탐색이 될 때 마다 해당 네트워크의 모든 노드가 탐색될 수 있도록 한다.