[programmers/python] 네트워크 개수 구하기 – Union-Find

문제 설명

- url : https://school.programmers.co.kr/learn/courses/30/lessons/43162

네트워크란 컴퓨터들 간에 정보 교환이 가능한 연결 상태를 의미한다.
예를 들어, 컴퓨터 A와 B가 연결되어 있고, B와 C도 연결되어 있다면 A와 C는 간접적으로 연결되어 있다고 본다.
이러한 경우 세 컴퓨터는 하나의 네트워크에 속한다고 판단한다.

---

입력 및 목표

• n: 컴퓨터의 수 (1 ≤ n ≤ 200)
• computers: n x n 크기의 2차원 배열로, computers[i][j] = 1이면 i번과 j번 컴퓨터가 연결되어 있음을 의미한다.
• computers[i][i] = 1은 항상 성립한다.
• 목표는 전체 컴퓨터를 연결 관계에 따라 그룹화하고, 총 네트워크의 개수를 구하는 것이다.

---

해결 전략

이 문제는 그래프에서 연결된 집합의 수를 묻는 전형적인 문제이다.
DFS나 BFS로 해결할 수도 있지만, Union-Find (서로소 집합) 알고리즘을 이용하면 더 직관적으로 해결할 수 있다.

Union-Find는 각 노드(컴퓨터)의 대표 루트를 추적하여, 연결된 노드끼리는 하나의 집합으로 병합하는 구조이다.
최종적으로는 각 노드의 루트를 기준으로 중복을 제거하면 전체 네트워크 수를 구할 수 있다.

---

구현

import sys
sys.setrecursionlimit(1000000)

def solution(n, computers):
    parents = [i for i in range(n)]  # 자기 자신이 부모이다.

    def find(a):
        if parents[a] != a:
            parents[a] = find(parents[a])  # 경로 압축을 적용한다.
        return parents[a]

    def union(a, b):
        pa = find(a)
        pb = find(b)
        if pa != pb:
            parents[pb] = pa  # 두 집합을 병합한다.

    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1 and i != j:
                union(i, j)  # 연결된 노드들을 하나의 집합으로 병합한다.

    # 모든 노드의 루트를 찾아 중복을 제거하고, 그 수를 반환한다.
    return len(set(find(i) for i in range(n)))

---

동작 예시

print(solution(3, [[1,1,0], [1,1,0], [0,0,1]]))  # 출력: 2
print(solution(3, [[1,1,0], [1,1,1], [0,1,1]]))  # 출력: 1

• 첫 번째 예제에서는 0번과 1번이 연결되어 하나의 네트워크를 이루고, 2번은 따로 떨어져 있으므로 총 2개의 네트워크가 존재한다.
• 두 번째 예제에서는 0번, 1번, 2번이 모두 연결되어 있으므로 하나의 네트워크만 존재한다.

---

시간 복잡도

• 모든 노드 쌍을 확인하는 반복문은 O(n²)이다.
• Union-Find 연산은 경로 압축을 통해 거의 O(1)에 수렴하므로 전체적으로 O(n²)의 시간 복잡도를 갖는다.
• n이 최대 200이므로 충분히 빠르게 실행 가능하다.