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

• 출처: 프로그래머스 43162
• 분류: DFS/BFS · Lv.3

문제

컴퓨터 수 n과 연결 정보 인접 행렬 computers가 주어진다. 직접 또는 간접으로 연결된 컴퓨터끼리 하나의 네트워크를 이룰 때, 네트워크의 개수를 반환한다.

핵심

그래프의 연결 요소(connected component) 개수를 구하는 문제다. 미방문 노드에서 DFS를 시작할 때마다 네트워크 1개를 발견한 것이다.

풀이

#include <vector>
using namespace std;

void dfs(int node, const vector<vector<int>>& computers, vector<bool>& visited) {
    visited[node] = true;
    for (int i = 0; i < (int)computers.size(); i++) {
        if (!visited[i] && computers[node][i])
            dfs(i, computers, visited);
    }
}

int solution(int n, vector<vector<int>> computers) {
    vector<bool> visited(n, false);
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, computers, visited);
            count++;
        }
    }
    return count;
}

메모

• 인접 행렬이 주어지므로 computers[node][i] == 1이면 연결이다. computers[i][i]는 항상 1이지만 visited에 의해 자기 자신으로의 재귀는 발생하지 않는다
• visited를 참조로 넘긴다. DFS가 방문 표시를 하면 다른 DFS 호출에서도 반영되어야 한다
• n ≤ 200이므로 재귀 깊이도 최대 200이다. 스택 오버플로우 걱정 없다
• BFS로 바꾸려면 DFS 함수를 큐 기반으로 변경하면 된다. 결과는 동일하다
• Union-Find로도 풀 수 있다. 인접 행렬을 순회하면서 연결된 쌍을 union하고, 최종 루트의 개수를 세면 된다

복잡도

풀이	시간	공간
DFS (인접 행렬)	O(N²)	O(N)
Union-Find	O(N² · α(N))	O(N)