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

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   컴퓨터 A와 컴퓨터 B가 연결되어 있고, 컴퓨터 B와 컴퓨터 C가 연결되어 있으면 컴퓨터 A와 컴퓨터 C도 연결되어 있다고 할 수 있다. 즉, 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있다. 이때 네트워크의 개수를 구하는 문제이다.

   컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 주어진다. 제한 사항은 다음과 같다.

 

• 1 ≤ n ≤ 200
• 각 컴퓨터는 0부터 n-1인 정수로 표현한다.
• computers[i][j]이 1인 경우, i번 컴퓨터와 j번 컴퓨터가 연결되었음을 의미한다.
• computers[i][i]는 항상 1이다.

---

접근 방식

   DFS의 개념을 이용해 문제를 해결하였다. 한 컴퓨터에 대해 DFS를 이용해 연결된 모든 컴퓨터를 찾으며 방문 여부를 표시한다. 이 과정이 하나의 네트워크를 찾는 과정이다. 만약 방문 여부 배열에서 아직 방문하지 않은 컴퓨터가 존재하는 경우, 해당 컴퓨터에 대해 이전 과정을 반복한다. 최종적으로 반복한 과정의 수가 구하고자 하는 네트워크의 수이다.

   예제를 통해 알아보자. 다음과 같이 방문 여부를 저장할 배열과, 0 ~ 5번의 컴퓨터가 연결되어 있다.

 

 

   먼저 0번 컴퓨터부터 DFS를 진행하여 같은 네트워크에 있는 컴퓨터를 탐색한다. 0과 연결된 1, 1과 연결된 2까지 탐색 후 종료되며 방문 여부도 true(1)로 초기화된다.

 

 

   0번 컴퓨터에 대해 탐색이 끝났으니 이제 1번 컴퓨터에 대해 탐색을 진행한다. 하지만 이전 탐색과정에서 1번 컴퓨터의 방문 여부는 1로 초기화되었기 때문에 탐색을 중단하고 다음 컴퓨터로 넘어간다. (2번 컴퓨터도 동일)

 

 

   3번 컴퓨터는 처음 방문하기 때문에 탐색을 진행한다. 3번과 연결된 4번 컴퓨터까지 탐색 후 탐색이 종료된다.

 

 

   5번 컴퓨터에 대해서도 동일한 과정을 거친다. 결과적으로 문제에서 요구하는 네트워크의 수는 방문 여부를 체크하며 DFS를 수행한 횟수이다.

---

코드

public class 프로그래머스43162번 {
    //방문 여부 저장
    static boolean[] visited;

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

        //네트워크가 여러 개인 경우 DFS로 모든 컴퓨터를
        //한 번에 찾을 수 없음
        for (int i = 0; i < n; i++) {
            //재방문 방지
            if (visited[i]) continue;
            DFS(computers, i);
            //네트워크 수 증가
            count++;
        }
        return count;
    }

    public void DFS(int[][] computers, int cur) {
        //방문 여부 표시
        visited[cur] = true;
        for (int next = 0; next < computers.length; next++) {
            //방문한 적이 없고, 연결된 컴퓨터인 경우만 DFS 진행
            if (visited[next] || computers[cur][next] == 0) continue;
            DFS(computers, next);
        }
    }
}