[알고리즘 문제 풀이][유니온파인드] 백준 20040번 - 사이클 게임

백준 20040번 사이클 게임입니다.

(Union Find 혹은 Disjoint Set)

 

- 문제 설명: https://www.acmicpc.net/problem/20040

- 문제 풀이:

 

본 문제는 일반적으로 유니온 파인드를 이용하는 문제입니다. 각 정점마다 연결된 부모를 관리해주는데, 서로 다른 그룹에 속한 정점을 합치게 되면 (Union) 각 그룹의 최상위 부모를 찾아서 (Find) 두 부모 중 하나를 부모로 만들어줍니다. 

유니온 파인드 개념에 대해 알지 못한다면 아래 개념을 참고하시거나, 간단한 유니온 파인드 기초문제부터 풀어보시는 것을 추천드립니다.

* 유니온 파인드란? https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

* 유니온 파인드 유튜브 설명: https://www.youtube.com/watch?v=AMByrd53PHM 

 

- 코드 (Python): 

import sys
input = sys.stdin.readline


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


def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
        return True
    elif a < b:
        parent[b] = a
        return True
    else:
        return False


N, M = map(int, input().split())
parent = [i for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if union(a, b):
        continue
    else:
        print(i+1)
        break
else:
    print(0)

 

 

- 실수 포인트 & 반례:

1. 런타임 에러

 

Union Find 를 구현할 때 재귀로 구현하다 보면, 런타임에러가 발생할 수 있습니다.

파이썬에서 (1) 재귀로 인한 런타임 에러의 경우 코드 맨 윗줄에 아래와 같이 추가를 해주시면 됩니다.

import sys
sys.setrecursionlimit(10**6)

혹은 (2) 재귀함수를 while 문으로 변경하는 방법도 있습니다.

(참고: https://www.acmicpc.net/board/view/92706)

while x != parent[x]:
	x = parent[x]
return x

 

2. 메모리 초과

 

PyPy3 로 제출시 메모리 초과, Python3 로 제출시 시간 초과가 나는 현상은 아래와 같이 Union Find 최적화 방법으로 해결할 수 있습니다. Union Find 최적화 방법은 (1) Path Compression (경로 압축) 과 (2) Union by Rank 가 있습니다. 

(참고: https://algorithms.tutorialhorizon.com/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/)

 

(1) 경로압축은 find 함수에서 최상위 부모를 찾을 때마다, 부모를 이 때 찾은 최상위 부모로 업데이트하는 방식입니다. 이렇게 하면 나중에 동일한 값의 최상위 부모를 찾을 때, 시간이 엄청나게 절약됩니다.

def find(a):
    if parent[a] == a:
        return a
    parent[a] = find(parent[a])
    return parent[a]

(2) Union by Rank 는 아래와 같이 구현할 수 있습니다. 항상 작은 값 기준으로 혹은 항상 큰 값 기준으로 합치도록 하면, 트리의 높이가 낮아져서 시간이 빨라지는 효과가 있습니다.

// Union 함수 내부

if parent[a] < parent[b]:
    parent[parent[a]] = parent[b]
else:
    parent[parent[b]] = parent[a]

 

3. 시간 초과

 

시간초과가 나는 경우, 2번에서와 같이 (1), (2) 최적화 방법이 모두 적용되었는지 확인이 필요합니다. 그래도 시간 초과인 경우 input 함수로 입력을 받는게 시간이 오래 걸렸기 때문일 수 있습니다. 코드 맨 윗줄에 아래와 같이 추가하여 해결할 수 있습니다.

import sys
input = sys.stdin.readline