백준 #20040 - [G4] 사이클 게임 : 그래프사이클, 유니온파인드

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

(python3)

그래프의 대표 유형중 하나인 사이클 존재 유무 탐색 문제입니다. 그래프 사이클 탐색의 경우 유니온 파인드 알고리즘으로 해결할 수 있습니다.

 

유니온 파인드

이어진 점들을 하나의 그룹으로 표현하는 방식입니다. 가장 직관적인 접근으로는

 

그룹 A와 B가 합쳐지는 경우 이렇게 모든 점들을 탐색하면서 A 를 B 로 편입시키는 방법입니다. 다만 이 방법을 사용하게 되면 새로운 선이 하나 추가될때 마다 모든 점의 그룹 상태를 모두 확인하여 바꿔야하기에 점이 많아질수록 연산 부담이 커집니다.

 

이 연산을 획기적으로 줄이는 방식이 union find 가 되겠습니다. 

핵심 아이디어는 각 점은 자신의 부모 노드만 저장하고 있고, 필요시마다 해당 점부터 부모 노드들을 타고 올라가서 각 그룹의 대표 (root) 점을 확인하겠다는 것입니다. 이렇게 타고 올라가서 그룹 대표를 찾는 과정을 find, 두 그룹을 합치는 과정을 union (A 그룹을 B 그룹에 병합시킨다고 하면, A 그룹 대표의 부모 (현재는 root 이기 때문에 부모가 없는 상태) 를 B 그룹 대표로 놓는 방식) 이라고 표현하면서 union find 알고리즘이 완성됩니다.

 

위에서 표현한 방식의 경우 find = O(1), union = O(점의 개수 N) 이 되겠고,

union find 의 경우 find = O(그룹 트리 깊이)*2, union = O(1) 이 됩니다.

N 이 크면 클수록 union find 의 강점이 커지겠습니다.

 

( 이 문제의 경우 점 개수 최대 500,000개, 시행 횟수 최대 1,000,000 회로 직관적 방식을 채택하면 5천억회의 연산이 일어나므로 일반적인 시간인 1억회에 1초로 잡는다면 5천초.. 예상해볼 수 있습니다. )

union find 의 시간복잡도는 각 그룹 트리들의 깊이가 결정짓습니다. 그룹 트리들이 한줄로 이어지는 경우가 최악의 경우가 되겠습니다.

 

보드게임 마스크맨을 플레이해보셨다면, 마스크맨의 진행 방식과 유니온 파인드가 유사하다고 생각됩니다.ㅎㅎ

 

구현 코드

def solution(input) : 
	# 입력받기
    N, M = list(map(int, input().split())) # N : num of points, M : turns
    union_list = [i for i in range(N)]
    turns = []
    for _ in range(M) :
        turns.append(tuple(map(int, input().split())))

 	# find 구현 (점 p가 속한 그룹의 리더 찾기)
    def find(p) :
        while union_list[p] != p :
            p = union_list[p]
        return p
    # find & union : (점 p1과 p2가 속한 그룹의 리더를 찾고 리더가 서로 다르면 병합, 같으면 같다는걸 리턴)
    def union_find(p1, p2) :
        rp1 = find(p1)
        rp2 = find(p2)
        if rp1 != rp2 :
            union_list[rp2] = rp1
        else :
            return -1
            
	# 유니온 파인드 진행
    for i,(p1,p2) in enumerate(turns) :
        if union_find(p1,p2) == -1 :
            print(i+1)
            return
    print(0)
    
solution(input)