[BOJ] 20040 : [유니온파인드](Python)

문제 링크

https://www.acmicpc.net/problem/20040

20040번: 사이클 게임

소스 코드

import sys
sys.setrecursionlimit(10**6)

def main():
    n, m = map(int, sys.stdin.readline().strip().split())
    parents = [x for x in range(n)] # 부모 노드 리스트

    def root(x):
        if x != parents[x]: # 자기 자신이 될 때까지 재귀
            parents[x] = root(parents[x])
        return parents[x]

    def union(a,b,cnt):
        global answer
        a, b = root(a), root(b)
        if a != b: # 작은 것이 부모, 큰 것이 자식
            parents[max(a,b)] = min(a,b)
        elif answer == 0: # 최초의 사이클
            answer = cnt

    for cnt in range(m):
        a, b = map(int, sys.stdin.readline().strip().split())
        union(a,b,cnt+1)
    
    print(answer)

if __name__ == '__main__':
    answer = 0
    main()

 

해설

• 유니온 파인드

확실히 쌩 기본 유형에 비해서 약간 까다로운 부분이 있네요.

코드로 구현하는게 복잡하지는 않지만 신경쓰지 않으면 은근 꼬이는 느낌이었습니다.

---

시간 복잡도

간선의 개수 m만큼 입력을 받아 union-find를 수행하므로 기본적으로 O(m)의 시간복잡도를 갖습니다.

거기에다가 일반적으로 union-find의(경로압축이 적용된) 시간복잡도는 O(log n)으로 알려져 있습니다.

그런데 알고보니 정확히는 log n이 아니더라구요.

아커만(Ackermann) 함수라는 것의 역함수인 α(n) 가 정확한 표기라고 하네요.

 

정리하면 O(m α(n))의 시간복잡도를 갖는 알고리즘이고, α(n)는 사실상 상수와 다름없는 수준이라고 합니다.

---

Union-Find

이 논리 자체는 기본 유형과 동일합니다.

 

Find의 경우 root 함수로 구현했습니다.

이때 부모노드가 자기 자신과 동일해질 때까지 재귀적으로 탐색을 반복하게 되어있구요,

그 과정에서 지나온 경로에 해당하는 노드들의 부모 노드도 한꺼번에 최상단 부모 노드를 가리키게 됩니다.

 

Union의 경우 a와 b, 둘 중 더 작은 숫자가 부모 노드가 될 수 있도록 함수를 작성했습니다.

def root(x):
    if x != parents[x]: # 자기 자신이 될 때까지 재귀
        parents[x] = root(parents[x])
    return parents[x]

def union(a,b,cnt):
    global answer
    a, b = root(a), root(b)
    if a != b: # 작은 것이 부모, 큰 것이 자식
        parents[max(a,b)] = min(a,b)

---

한 번만 갱신

조금 애매했던 부분이 사이클이 완성되었을 때 break나 exit을 걸어버리면 입력 오류가 발생할 수 있다는 점이었습니다.

그래서 제일 바깥에 answer 변수를 만들고, 이를 함수 내에서는 global 변수로 선언하여 이 값이 0일 때만 값을 갱신하도록 했습니다.

사이클이 한 번 완성되고 나서 이후에 또 사이클 판정을 받을 수도 있는데, 그때는 answer의 값이 0이 아니므로 값이 갱신되지 않습니다.

elif answer == 0: # 최초의 사이클
    answer = cnt