[BOJ][Python]20040 풀이

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

20040번: 사이클 게임

import sys
ssr = sys.stdin.readline

def find(node):
    if uf[node] == node:
        return node
    else:
        uf[node] = find(uf[node])
        return uf[node]

def union(node1, node2):
    root1 = find(node1)
    root2 = find(node2)
    if root1 != root2:
        if rank[root1] < rank[root2]:
            uf[root1] = root2
        elif rank[root1] == rank[root2]:
            uf[root1] = root2
            rank[root2] += 1
        else:
            uf[root2] = root1
        return False
    else:
        return True
        
n, m = map(int, ssr().split())
uf = [i for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(m):
    node1, node2 = map(int, ssr().split())
    result = union(node1, node2)
    if result:
        print(i+1)
        break
else:
    print(0)

단계별 풀어보기의 유니온 파인드 마지막 문제입니다. 사실 유니온 파인드 문제를 다 풀기 위해서 시작했던 것은 아니고, 그냥 클래스 4 문제를 풀다가 유니온 파인드가 제가 지금 고민 중인 문제를 푸는데에 도움을 줄 것 같아서 익숙해지기 위해서 되는대로 풀었고 유니온 파인드를 그 문제에 어떻게 적용을 시킬 수 있을지 감을 잡아서 적용해서 예제는 통과했지만 제출하니까 시간 초과로 틀리게 되었습니다. 루비 1이었으니 쉽지는 않을 것이라고 생각했지만 일단 실마리를 하나 찾은 것 같다는 생각이 드네요.

 

이 문제와는 별로 상관이 없는 말만 늘어놓았습니다. 이 문제는 유니온 파인드를 이용해서 어느 시점에 사이클이 생기는지를 출력하는 문제입니다. 저도 처음엔 어떻게 구현을 할까 조금 고민을 했는데, 생각해보면 간선을 하나씩 생성해서 사이클을 만드는 시점을 출력한다는 건 사이클을 구성하기 위한 모든 노드가 이미 연결이 되어있는 상태에서 마지막으로 선을 하나 추가하면 된다는 뜻이니까 이미 뿌리 노드가 동일한 노드 끼리 간선을 연결할 때가 사이클이 생기는 시점이라고 생각해볼 수 있겠습니다. 그래서 union 함수를 기본 형태에서 조금 변형시켜서 뿌리 노드가 같은 경우에 union을 시켰다면 True를 리턴해서 그 때의 순서를 출력하도록 코드를 짜봤습니다. 이게 유니온 파인드라는 생각이 안들었다면 모든 경우를 다 DFS를 돌려가면서 체크를 했어야 할테니 아마 시간초과로 풀지 못하게 될 것 같네요.