BaekJoon 20040번 : 사이클 게임 (python)

BaekJoon 20040번 : 사이클 게임 (G4 50.415%)

사이클 게임 문제

Union-Find 알고리즘을 활용한 문제이면서 효율성을 챙겨야 하는 문제이다.

• 문제의 조건에서 최초로 사이클이 완성되는 순간은 '한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다'고 명시하였는데 사실상 트리로 시각화하였을 때 보면 새로 들어온 입력에 대해서 root값이 이미 통일되어있는 최초의 시점을 찾으면 되는 문제이다.
• 입력받은 a,b가 만약 union과정을 하기전에 이미 연결되어있는 상황이라면 해당 문제의 조건을 만족하게 된다.
• 만약 루트 노드값이 다르다면 a,b를 union과정을 통해 루트 노드를 통일시켜주게 된다.

느낀점

이 문제를 통해 경로 압축과 Union by rank을 통한 효율성 챙기는 부분이 Union-Find 알고리즘에서 중요하다는 것을 알았다.
경로 압축은 지금까지 지나온 값들을 모두 루트 노드로 변환해주며 효율성을 챙길 수 있고 Union by rank를 통해 트리의 높이를 최소한으로 높여주어 시간이 빨라지는 효과를 발생시킨다.

---

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def find(x) :
    if root[x] != x :
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    Nx = find(x)
    Ny = find(y)
    if Nx != Ny :
        if rank[Nx] > rank[Ny] :
            root[Ny] = root[Nx]
        elif rank[Nx] < rank[Ny] :
            root[Nx] = root[Ny]
        else :
            root[Ny] = root[Nx] 
            rank[Nx] += 1

n, m = map(int,input().split())
root = list(range(n))
rank = [1] *n
count = 0
for i in range(m) :
    a, b = map(int,input().split())
    if find(a) == find(b) and count == 0:
        count = i+1
    union(a,b)
print(count)