[프로그래머스 / Javascript] 네트워크 (Lv 2)

문제 자체는 짧다. 컴퓨터 n대의 연결 정보가 인접 행렬 computers로 주어지고, 서로 직간접적으로 연결된 컴퓨터들은 하나의 네트워크다. 네트워크가 총 몇 개인지 세면 된다.

n = 3, computers = [[1,1,0],[1,1,0],[0,0,1]]  →  2
n = 3, computers = [[1,1,0],[1,1,1],[0,1,1]]  →  1

첫 번째 예제를 보면 0번과 1번이 연결되어 있고 2번은 혼자다. 그래서 네트워크 2개.

접근

문제를 읽고 나면 사실 답이 정해져 있다. "직접 연결이든 간접 연결이든 이어져 있으면 같은 네트워크"라는 정의가 그래프에서 말하는 연결 요소(Connected Component) 그 자체이기 때문이다. 컴퓨터가 정점이고 연결이 간선이니, 연결 요소가 몇 덩어리인지 세면 끝난다.

세는 방법은 단순하다. 0번부터 순서대로 돌면서, 아직 방문 안 한 컴퓨터를 만나면 거기서 DFS를 돌려 이어진 컴퓨터를 전부 방문 처리한다. DFS를 새로 시작한 횟수가 곧 네트워크 개수다. 이미 방문한 컴퓨터는 어딘가의 DFS에서 쓸려간 것이므로 건너뛰면 된다.

풀이

function solution(n, computers) {
    const visited = new Array(n).fill(false);
    let answer = 0;

    const dfs = (node) => {
        visited[node] = true;
        for (let next = 0; next < n; next++) {
            if (computers[node][next] === 1 && !visited[next]) {
                dfs(next);
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            answer++;
        }
    }

    return answer;
}

입력이 인접 리스트가 아니라 인접 행렬이라는 점만 주의하면 된다. node의 이웃을 찾으려면 computers[node] 행을 처음부터 끝까지 훑어야 해서, DFS 안에 0 ~ n-1 루프가 들어간다.

computers[i][i]가 항상 1이라는 조건은 신경 쓸 필요가 없었다. dfs(i)에 들어가는 순간 visited[i]를 true로 찍기 때문에, 자기 자신으로 가는 간선은 !visited[next] 조건에서 알아서 걸러진다.

복잡도

인접 행렬 기반이라 O(n²)이다. n이 최대 200이니 4만 번 연산이면 끝나고, 재귀 깊이도 최악의 경우 200이라 스택 걱정도 없다. 이 제약이었기 때문에 재귀 DFS를 편하게 쓸 수 있었다. n이 10만쯤 됐다면 인접 행렬부터 메모리가 터지니 문제 입력 자체가 달랐을 것이다.

Union-Find는?

연결 요소 하면 Union-Find도 같이 떠오르는데, 이 문제에서는 꺼내지 않았다. 연결 정보가 처음부터 전부 주어져 있고 개수를 딱 한 번만 세면 되는 상황에서는 DFS가 코드도 짧고 읽기도 쉽다. Union-Find가 필요해지는 건 간선이 실시간으로 추가되면서 "지금 네트워크 몇 개?"를 반복해서 물어볼 때 쓰면 되지 않을까 싶다.