https://www.acmicpc.net/problem/20040
20040번: 사이클 게임
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한
www.acmicpc.net
본 문제는 전형적인 유니온 파인드 문제이다. 혹시라도 유니온-파인드 알고리즘이 생소하신 분은 이 링크를 참조하여 훑어보기 바란다.
유니온-파인드를 이해하고 잘 적용할 수 있다면 비교적 평이한 문제일 수 있지만,
주의해야 할 부분이 있어서 포스팅하게 되었다.
파이썬 언어를 사용할 경우, 스택 깊이가 1000으로 기본 설정되어있는데, 이 깊이를 키우기 위해서는 아래와 같이 해야 한다.
sys.setrecursionlimit(10000) <-원하는 수 삽입유니온-파인드에서 find함수는 보통 아래와 같이 구현된다.
def find(a):
if root[a]==a:return a
root[a]=find(root[a])
return root[a]여기서 find(root[a])를 하는 부분 때문에 깊이가 깊은 재귀 함수의 형태가 될 수 있는 것이다.
유니온 함수에서 특정 조건을 걸어두지 않고 그냥 연결해주거나 하는 방식을 사용했을 때, 파인드 함수로 루트를 찾아나가다 보면
최악의 경우(worst case) 모든 정점을 한 번씩 다 거치기 때문이다.
그래서 유니온-파인드 문제를 파이썬으로 풀 때는 문제에서 주어지는 정점 갯수 등의 조건을 잘 활용하여 그만큼의 재귀 깊이를 확보해두어야 한다.
<주요 알고리즘>
유니온 파인드 (union-find)
<코드>
아래에서 보면 정확하게 정점 개수 50만을 주는 것이 아니라 약간의 여유분을 위해 +10을 해주었다.
import sys
si = sys.stdin.readline
sys.setrecursionlimit(500000+10)
n, m = [int(e) for e in si().split()]
assert n<=500000
roots, ans= [i for i in range(n)], 0
def find(a):
if roots[a] == a:
return a
roots[a] = find(roots[a])
return roots[a]
def union(a, b):
a,b=find(a),find(b)
roots[a]=b
for i in range(1, m+1):
a, b = [int(e) for e in si().split()]
if find(a) == find(b):
ans = i
break
else:union(a, b)
print(ans)
