[BOJ / 백준 20040번][PYTHON] 사이클 게임 (유니온 파인드)

유니온 파인드 마지막 예제이다.

 

이런 유니온 파인드 같은 알고리즘 한해서 나오는 예제 같은 경우는 문제가 다양한 느낌은 아니다. 뭔가 구조를 활용해서 문제와 싸운다기 보다는 그저 유니온 파인드를 구현해놓고 살짝씩 바꿔가며 해결해가는 느낌이다.

 

일단 문제를 읽어보면 사이클에 대한 문제해결을 요구한다.

지금까지는 같은 집합임을 물어봤다면, 이번에는 간선을 긋는다는 점에서는 같은 집합임을 물어봤으나 사이클이라는 조건을 추가하여 첫 사이클이 언제 발생하는 지를 출력해야한다.

 

그렇다면 사이클이 어떤 경우일 지를 생각해보면

1. 같은 집합에 있어야 한다.

2. 이미 같은 집합에 있어야 한다.

 

이렇게 순서대로 생각하는 것이 옳다. 즉, 컴퓨터 속에 내가 있다는 가정으로 상황을 계속 판단해본다고 할 때 입력이 들어올 때마다 간선을 계속 그을 것이다. (같은 집합으로 만들 것이다.) 거기서 간선을 그으려고 확인을 하는데 "어? 이미 둘이 같은 집합이네" 이 순간 사이클이 만들어지게 될 것이다. 이제 구현을 한다면 어떻게 할 것인가. 입력이 들어올 때 두 점이 같은 집합인 지를 확인하는 코드를 작성하고 그게 첫번째인 경우를 저장해두고 나중에 출력을 하면 될 것이다. 여기서 저장된 것이 없다면 사이클이 발생하지 않는 것이고 저장된 것이 있다면 사이클이 발생한 상황이다. 구현은 아래와 같다.

import sys
sys.setrecursionlimit(10**5)
def find(x):
    if arr[x] == x:
        return x
    
    arr[x] = find(arr[x])
    return arr[x]

def union(x, y):
    a = find(x)
    b = find(y)

    if a< b:
        arr[b] = a
    else:
        arr[a] = b        
   
n,m = map(int, sys.stdin.readline().split())
flag = True
arr = [i for i in range (n)]

for i in range (m):   
    a,b = map(int, sys.stdin.readline().split())
    if find(arr[a]) == find(arr[b]) and flag == True:
        count = i
        flag = False
    else:
        union(a,b)

if flag == True:
    print(0)
else:
    print(count+1)

유니온 파인드의 경우 find 함수가 재귀로 들어가기 때문에 어느 정도 숫자에서 어느 정도 재귀로 들어가는 지 확인할 수는 없지만 파이썬 최대 재귀에 접근하는 경우가 있다. 그리하여 sys.setrecursionlimin()을 통해서 최대 재귀에 대해서 설정을 해줘야 한다. 이것을 하지 않으면 runtime error 중 recursion관련한 에러가 나올 수 있다.

이렇게 난리가 나게 된다.