[Python] 20040번 사이클 게임

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

20040번: 사이클 게임

---

 

22/10/01

 

 

사이클을 만들 수 있는지의 여부와, 만들 수 있다면 처음 사이클이 만들어졌을 때의 차례를 출력하는 문제로, 유니온-파인드 알고리즘을 활용하여 쉽게 풀 수 있는 문제이다.

 

만약 유니온-파인드 함수나 분리집합 자료 구조에 관해서 잘 모르는 상황이라면 공부를 먼저 하고 이 글을 보면 도움이 될 것이다.

---

 

문제 접근 방식:

 

 

이 문제에서 사이클이 만들어 진다는 뜻은, 이미 같은 선분으로 이었던 점끼리 다시 선분으로 잇는다는 뜻이다.

 

예를 들어, 내가 먼저 1번 점과 2번 점을 선분으로 이었다고 해보자.

 

이후 상대방이 2번과 3번을 선분으로 잇고, 다시 나는 3번과 4번을 잇고, 상대방이 4번과 2번을 잇는다고 해보자.

 

4번째 차례(상대방의 차례) 때, 이미 선분으로 이엇던 점(4번과 2번)끼리 다시 잇는 것이므로, 우리는 이 4번째 상황 때 사이클이 만들어졌다고 판단할 수 있는 것이다.

 

분리 집합 자료구조에 따르면, 각 차례 때마다 점들을 잇는 행위는 유니온 함수를 사용하는 것과 같은 행위라고 볼 수 있다.

 

때문에 유니온을 하기 전, 각 점의 대표노드가 서로 같은 경우, 이미 두 점은 선분끼리로 이어져있다는 뜻이므로, 그 차례 때 사이클이 만들어진다고 판단할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 20040번 사이클 게임
# 자료구조, 분리집합
'''
접근 방법:
이미 같은 그룹에 있는 애들끼리 유니온 하는 것이라면 사이클이 완성된 것으로 간주
'''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N, M = map(int, input().rstrip().split()) # 점의 개수와 진행 된 차례 수
reps = list(range(N))

def find(node):
    if reps[node] != node:
        reps[node] = find(reps[node])
    return reps[node]
def union(node1, node2):
    rep1 = find(node1)
    rep2 = find(node2)
    reps[rep2] = rep1

for time in range(1, M+1):
    i, j = map(int, input().rstrip().split())
    rep_i = find(i)
    rep_j = find(j)
    union(i, j)
    if rep_i == rep_j:
        print(time)
        break
else:
    print(0)