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

• 네트워크

풀이과정

• 모든 컴퓨터는 자기자신에 대해서 연결됨 상태로 주어지는 것을 이용한다.

기본적인 골자는 다음과 같다.

1. (i, i) 번 째 좌표에서 탐색을 시작한다. 탐색 시작시마다 이미 해당 컴퓨터를 확인했음을 표시한다.
   • i번 째 row를 통해 연결되어있는 컴퓨터들을 모두 확인한다.
   • 연결된 컴퓨터들의 번호를 k라 할 때 (k, k)번 째 좌표에서 다시 탐색을 시작한다. (DFS) 이미 확인되었음 표시가 있다면 스킵하고, 그렇지 않다면 그대로 진행한다.
2. 1번 과정에서 한 번 빠져나올 때 마다 식별한 네트워크의 갯수를 1 증가시킨다.
3. 더이상 탐색할 컴퓨터가 없으면 모든 탐색을 종료하고 식별된 네트워크의 총 갯수를 반환한다.

시나리오

n = 7 이고, 1-2-3과 4-5-6 및 7 으로 세 개의 네트워크를 가지는 경우를 가정했을 경우 풀이의 진행과정은 다음과 같다.

1. 먼저, 문제에서 주어지는 computers 배열에 따라 연결됨(true), 연결되지 않음(false)으로 네트워크 배열을 만들어보면 다음과 같다.

2. 1번 컴퓨터에서 탐색을 시작한다. 1번 컴퓨터가 현재 추적중인 네트워크에 포함되었다는 의미로 위 표의 (1, 1)번 좌표의 값을 변경한다(T -> F). 그런 다음 1번 컴퓨터에 대한 row를 확인하면 1번 컴퓨터에 연결된 컴퓨터들을 알 수 있다. 아래 그림에서 붉은 사각형으로 표시된 2번, 3번 컴퓨터가 1번 컴퓨터에 연결되어있음을 볼 수 있다.
   즉, 다음 탐색 차례는 2번과 3번 컴퓨터이다.

3. 차례대로 2번 컴퓨터에서 다시 탐색을 시작한다. 위 2번 과정과 마찬가지로 2번 컴퓨터에 해당하는 (2, 2)번 좌표값을 먼저
   변경한다(T -> F). 그러면 여기서 2번 컴퓨터는 1번과 3번 컴퓨터에 연결되어 있음을 확인할 수 있다.
   즉, 다음 탐색 차례는 1번과 3번 컴퓨터이다.

4. 1번 컴퓨터에서 다시 탐색을 시작한다. 하지만 이 때에는 (1, 1)번의 좌표값이 false 이므로, 이 1번 컴퓨터는 이미 어느 네트워크에 연결되어있는지 확인이 완료되었음을 알 수 있다. 따라서 더이상의 탐색을 진행하지 않고 종료한다.
   그런 다음, 3번 과정의 나머지 연결된 컴퓨터인 3번 컴퓨터에서 다시 탐색을 시작한다. 앞서 과정과 마찬가지로 (3, 3)번 좌표값을 먼저 변경(T -> F)하고 연결된 컴퓨터를 찾는다.
   아래 그림과 같이 1번과 2번 컴퓨터와 연결되어 있음을 확인할 수 있다. 즉, 다음 탐색 차례는 1번과 2번 컴퓨터이다.

5. 과정 4의 결과에 따라 1번 컴퓨터에서 다시 탐색을 시작한다. 하지만 이미 (1, 1) 좌표값이 false 이므로 바로 탐색을 중단하고 다음 과정으로 넘어가 2번 컴퓨터에서 탐색을 다시 시작한다. 마찬가지로 (2, 2) 좌표값이 이미 false 이므로 2번 컴퓨터도 어느 네트워크에 소속되었는지 이미 확인이 완료되었으므로 탐색을 바로 종료한다.
6. 더이상 3번 컴퓨터에 연결되어있는 네트워크가 없으므로 하나의 네트워크에 대한 탐색이 종료되었다. 탐색한 네트워크의 갯수를 하나 증가시킨다. 한 번의 DFS 사이클이 종료되었다.
7. 과정 2를 2번 컴퓨터부터 다시 시작한다(새로운 DFS 사이클의 시작). 이번에도 마찬가지로 (i, i) 좌표값이 false이면 스킵하고, True이면 위 과정처럼 탐색을 진행한다. 이 예시와 같은 경우 2번과 3번 컴퓨터에서는 스킵이 발생하고, 4번 컴퓨터에서 탐색을 시작하면 1-2-3번 컴퓨터와 같은 방식으로 4-5-6번 컴퓨터가 속한 네트워크를 식별할 수 있다.
8. 이후 다시 5번, 6번 컴퓨터에서 시작하는 탐색이 스킵되고 마지막 7번 컴퓨터만 속한 네트워크가 탐색된다.
9. 더이상 탐색할 컴퓨터가 없으므로 이상의 과정을 통해 최종 네트워크의 갯수를 알 수 있다.

Code

• 위 과정에 현재까지 식별된 컴퓨터의 갯수를 세는 과정(아래 코드의 identifiedComputersCount)을 별도로 추가하면 마지막 번호의 컴퓨터를 포함한 뒷 번호 컴퓨터들이 다른 네트워크에 속해 있을 때 약간의 효율성 향상을 기대할 수 있을 것 같았다.

• 예를 들어, 문제 조건의 최댓값인 200대의 컴퓨터가 주어졌을 때 모든 컴퓨터가 하나의 네트워크에 연결되어 있다면 첫 번째 탐색이 끝난 시점에서 식별된 컴퓨터의 갯수가 200대이므로 2번 컴퓨터부터 200번 컴퓨터까지 [탐색 시작 -> false값 확인 후 스킵] 하는 과정을 거치지 않고 루프를 종료할 수 있다.

• 하지만 마지막 번호의 컴퓨터(또는 굉장히 뒷 번호의 컴퓨터)가 혼자만 격리되어있는 네트워크에 속해있는 경우 모든 루프를 다 돎과 동시에 매번 식별된 컴퓨터의 갯수를 체크하는 과정이 추가되는 것이므로 약간의 효율성 저하를 발생시킬 수 도 있다.

• 문제에 주어진 테스트 케이스들에 대해서는 대체적으로 약간의 효율성 향상을 확인할 수 있었으므로 아래 코드에는 이 과정을 추가하였다.

  class Solution {
    public static int identifiedComputersCount = 0;
  
    public int solution(int n, int[][] computers) {
        boolean[][] connected = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                connected[i][j] = computers[i][j] == 1;
            }
        }
  
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (connected[i][i]) {
                dfs(connected, i);
                count++;
            }
  
            if (identifiedComputersCount == n) {
                break;
            }
        }
  
        return count;
    }
  
    private void dfs(boolean[][] connected, int i) {
        if (i < 0 || i >= connected.length || !connected[i][i]) {
            return;
        }
  
        connected[i][i] = false; // mark as visited
        identifiedComputersCount++;
  
        for (int j = 0; j < connected.length; j++) {
            if (connected[i][j]) {
                dfs(connected, j);
            }
        }
    }
  }

결과