[알고리즘 문제 풀이][유니온파인드] 백준 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 가 있습니다.
(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