[프로그래머스 Level 3] 네트워크

문제

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

 

제한 사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

---

풀이

 

아주 간단한 우선 탐색 문제였다. 왜 Level 3 문제 인지 모르겠다. BFS, DFS 어느 것으로 풀어도 풀 수 있다. 나는 너비 우선 탐색(BFS)로 접근했다.

 

예를 들어보자,

 

n = 3이고, computers가 [[1, 1, 0], [1, 1, 0], [0, 0, 1]]로 주어졌을 때,

 

BFS를 1(=0, 정점(컴퓨터)는 0번부터 시작하므로)번부터 순회를 하게 되면 [1, 1, 0]에서 2(=1)번과 연결되어 있음을 알 수 있다. 하지만 2번 컴퓨터의 연결 상태는 [1, 1, 0]이므로 3(=2)번 컴퓨터와 연결되어 있지 않다.

 

그 다음 2번 컴퓨터를 시작으로 순회하게 되면, 2번 컴퓨터는 앞에서 방문했기 때문에 다시 순회할 필요가 없다.

 

마지막으로 3번 컴퓨터에서 순회를 하게 되면, 3번 컴퓨터는 방문하지 않았기 때문에 한 번 더 카운트하고, 연결 상태 [0, 0, 1]을 보면 단독으로 사용되는 것을 알 수 있다. 즉, 2개의 네트워크가 사용되고 있다.

 

그림으로 나타내면 다음과 같다.

 

하나 더 예를 들면

 

n = 3이고, computers가 [[1, 1, 0], [1, 1, 1], [0, 1, 1]]로 주어졌을 때,

 

BFS를 1번 컴퓨터부터 순회를 하게 되면 [1, 1, 0]에서 2(=1)번과 연결되어 있음을 알 수 있다. 바로 2번 컴퓨터로 가서 연결 상태를 확인하면 [1, 1, 1]로 3(=2)번 컴퓨터와 연결되어 있음을 알 수 있다.

 

2, 3번 컴퓨터는 앞에서 연결되어 있음을 알았으므로(방문했음), 다시 순회할 필요가 없다.

 

즉, 하나의 네트워크에 모든 컴퓨터가 연결되어 있다. 그림으로 나타내면 다음과 같다.

 

 

이를 코드로 나타내면 아래와 같다.

 

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    private int[][] computers;
    private boolean[] visited;

    private int bfs(int v) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        visited[v] = true;

        while(!q.isEmpty()) {
            int w = q.poll();

            for(int n=0; n<computers[w].length; n++) {
                if(computers[w][n] == 0 || visited[n]) continue;

                visited[n] = true;
                q.offer(n);
            }
        }
        return 1;
    }

    public int solution(int n, int[][] computers) {
        this.computers = computers;
        visited = new boolean[n];

        int answer = 0;

        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                answer += bfs(i);
            }
        }
        return answer;
    }
}