악곱 == 악성곱슬

유니온 파인드

---

이 문제는 서로의 연결 여부를 확인하는 것이다. 우리는 여러가지 방법으로 풀 수 있지만, 유니온-파인드를 이용하는 방법이 연결 여부를 고려할 떄는 가장 먼저 떠오른다.

1. 유니온 파인드를 이용하여 parent 배열 정리
2. 아직 경로 압축이 덜 된 부분이 있으므로, 빈 집합 set을 선언하고, 빈 집합에 parent 배열을 find 연산을 한 결과를 넣는다.

find를 1에서 한번 2에서 한번 함으로 모든 경로가 압축되어 그룹의 개수를 구할 수 있는 상태가 되는 것이다.

이해가 쉽도록 하자면, 모든 노드들의 부모를 찾아서 이를 빈 집합에 넣는 것이다. 이를 통해 집합의 전체 개수를 파악할 수 있기 때문이다.

구현

---

def find(x, parent):
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(a, b, parent):
    a = find(a, parent)
    b = find(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution(n, computers):
    parent = [i for i in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            if computers[i][j] == 1:
                union(i, j, parent)
    count = set()
    for i in range(n):
        count.add(find(i, parent))

    return len(count)