[백준 20040 파이썬] 사이클 게임 (골드 4, 유니온 파인드)

알고리즘 유형 : 유니온 파인드
풀이 참고 없이 스스로 풀었나요? : O

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

SOLVE 1

weighted union find 풀이

import sys
input = sys.stdin.readline

# weighted union find

def find(x):
    if graph[x] < 0:
        return x
    
    graph[x] = find(graph[x])
    return graph[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return
    
    if graph[x] < graph[y]:
        graph[y] = x
    elif graph[x] > graph[y]:
        graph[x] = y
    else:
        graph[x] = y
        graph[y] -= 1
        
    return

n, m = map(int, input().split())
graph = [-1]*(n)
result = 0

for i in range(1, m+1):
    a, b = map(int, input().split())
    
    a = find(a)
    b = find(b)
    
    # union을 하기 전에 이미 두 노드가 한 그래프 내에 있다면(=루트
    # 노드가 서로 같다면), 이미 그은 선분은 다시 긋지않는다고 했으므로
    # 이미 경로가 있는 두 노드를 또 다른 경로를 하나 만들어주는 셈이
    # 되므로 사이클의 생성을 의미함.
    if a == b:
        result = i
        break
    
    union(a, b)
    
print(result)

SOLVE 2

union find 풀이

import sys
input = sys.stdin.readline

def find(x):
    if x == graph[x]:
        return x
    
    graph[x] = find(graph[x])
    return graph[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return
    
    if x < y:
        graph[y] = x
    else:
        graph[x] = y
        
    return

n, m = map(int, input().split())
graph = [i for i in range(n)]
result = 0

for i in range(1, m+1):
    a, b = map(int, input().split())
    
    a = find(a)
    b = find(b)
    
    if a == b:
        result = i
        break
    
    union(a, b)
    
print(result)

SOLVE 1) 풀이 요약 (weighted union find 풀이)

1. weighted union find로 입력받는 노드를 계속 연결해주면서, 그 때마다 find로 두 노드의 루트 노드를 비교하여 사이클 여부를 확인한다.

2. 두 노드를 입력받고, union을 하기 전에 두 노드의 루트 노드를 비교한다. 만약 루트 노드가 같다면, 이미 두 노드는 한 그래프 안에 존재한다는 뜻이다.

   문제에서 이미 그은 선분을 다시 긋지는 않는다고 했으므로, 입력받은 두 노드를 잇는 선분은 최초로 긋는 선분인데, 이미 두 노드 간의 경로가 존재한다는 것은 사이클을 의미하는 것이다.

   즉, 루트 노드가 같다면 그 때의 입력 순서 인덱스를 변수에 담고 break한다.

SOLVE 2 풀이 요약 (union find 풀이)

1. 위의 풀이와 거의 같고, weighted가 아닌 일반적인 union find로 푼 풀이이다.

   이 문제에선 별 차이가 없지만, 만약 데이터의 크기가 크다면, union을 하면서 트리의 깊이가 지나치게 깊어질 수 있으므로, 일반적인 union find에서 트리의 깊이를 저장해두는 rank 리스트를 따로 또 만들어주고, rank 값에 따라 트리를 어느 쪽으로 합칠 것인지 분기 if문을 만들어주면 트리 깊이를 줄일 수 있다.

   다만 이 경우에 rank 리스트를 만들었기에 공간 복잡도가 늘어나므로, 이를 해결한 것이 weighted union find 이다.

배운 점, 어려웠던 점

• 유니온 파인드 응용력을 기를 수 있어 유익했다.