코딩 테스트 합격자 되기 - 간단한 유니온-파인드 알고리즘 구현하기

문제 출처

풀이

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


def union(parents, x, y):
    root1 = find(parents, x)
    root2 = find(parents, y)

    parents[root2] = root1


def solution(k, operations):
    parents = list(range(k))
    n = k

    for op in operations:
        if op[0] == 'u':
            union(parents, op[1], op[2])
        elif op[0] == 'f':
            find(parents, op[1])
    
    n = len(set(find(parents, i) for i in range(k)))
    return n

풀이 설명

• 유니온 파인드 알고리즘을 구현한 코드이다
• 파인드 함수에서는 해당 노드의 루트함수를 찾는 함수인데 재귀방식으로 부모노드를 계속 구해가고 노드의 부모노드가 현재 노드와 같을경우 현재 노드를 리턴한다
• 유니온 함수는 두 노드를 합치는 함수인데, 두 노드의 루트노드를 찾은 후 한쪽 노드에 통합시켜 하나의 루트노드로 만들어준다
• 유니온, 파인드 과정을 진행하며 for문을 다돌았을 때 집합의 개수를 구해주면 된다