[Union-Find] Friend-Circle

Union-Find 알고리즘에 관한 설명은 나동빈님의 블로그에서 보고 이해했다.

Union-Find 알고리즘은 간단히 말하자면 합집합 찾는 알고리즘 다르게 말하자면 서로소(disjoint set)을 찾는 알고리즘이다.

원리 및 구체적인 구현 방법은 나동빈님의 블로그에 아주 상세히 설명되어 있다.

m.blog.naver.com/ndb796/221230967614

 

그 구현 및 실습은 leetcode의 Friend-Circle을 통해 구현해 보았다. 

find는 해당 노드의 제일 조상 노드를 찾는 함수이다.

union은 각 노드의 제일 조상 노드가 동일한 경우에 합치는 함수이다. Union-Find 문제에 따라서 union을 언제 해야하는 지는 달라질 수 있다.

 

 

from collections import defaultdict

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        parents = [x for x in range(len(M) + 1)]
        n = len(M)
        
        def find(x:int):
            if x == parents[x]:
                return x
            root = find(parents[x])
            parents[x] = root
            return root
        
        for r in range(n):
            for c in range(r, n):
            # 이 문제에서는 Union하는 순간을 잘 결정하는 것이 필요하다.
                if r != c and M[r][c] == 1:
                    u = find(r + 1)
                    v = find(c + 1)
                    if u != v:
                        parents[v] = u
        answer = [parent for index, parent in enumerate(parents) if index == parent and index > 0]
        return len(answer)