20040번 사이클 게임

문제

https://www.acmicpc.net/problem/20040
게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

풀이

이 문제는 분리 집합의 개념과 Union-Find 알고리즘을 알아야 풀 수 있다.

분리 집합 (Disjoint Set)

분리 집합 개념, 분리 집합 파이썬을 참고했다.
그래프 탐색을 통해 목표 지점을 확인하려 할 때, 계속 새로운 연결이 생긴다면 그럴때마다 다시 그래프 탐색을 진행해야하고 매우 오래걸릴 것이다.
이 때, 그래프 형태가 아닌 그룹으로 표현하여 소요되는 시간을 단축 시킬 수 있다.

분리 집합은 서로소 집합이라고도 한다.
전체집합 U, U의 분리 집합 A, B가 있을 때, 이미 존재하는 집합 U에 대해 겹치는 부분이 발생하지 않도록 모든 원소들을 분리한 부분집합을 말한다.

Union-Find 알고리즘

Union-Find는 이러한 분리 집합을 구현하는 알고리즘으로, 각 그룹을 트리의 형태로 표현한다.
트리는 항상 최상위 노드인 root 노드를 가지는데, 이 root 노드로 그룹을 구별한다. (root 노드는 부모 노드를 자기 자신으로 설정한다.)

만약 두 그룹 간에 새로운 연결이 만들어진다면 두 그룹의 root 노드가 같아지고 트리를 병합할 수 있게 된다.
그래서 이 알고리즘에서 필요한 연산은 다음과 같다.

• root 노드를 찾는 작업 (Find)

• 두 트리를 병합하는 작업 (Union)

# 각 집합의 대표노드를 찾는 함수
def find(n):
    if reps[n] != n:
        reps[n] = find(reps[n])
    return reps[n]

# 두 개의 집합을 합치는 함수
def union(node1, node2):
    rep1 = find(node1)
    rep2 = find(node2)
    reps[rep2] = rep1

예시로 1 ~ 6번 노드가 있다고 할 때, 처음엔 각 집합의 대표(root)가 자기 자신이 될 것이다.

reps = list(range(7))
# [0, 1, 2, 3, 4, 5, 6]

여기서 2번 노드가 1번 노드와 한 집합에 속하게 된다고 하면 2번 노드는 1번 노드를 가리키고, 총 5개의 집합이 된다.

reps[2] = 1
# [0, 1, 1, 3, 4, 5, 6]

이어서 4번과 5번 노드가 3번 노드를 가리키면 다음과 같이 된다.

reps[4] = 3
reps[5] = 3
# [0, 1, 1, 3, 3, 3, 6]

이를 이용해 문제를 보면
플레이어 순서는 중요하지 않고 사이클이 발생하는 시점이 중요하다.
사이클이 발생한다는 것은 두 노드의 부모가 같다는 뜻이다.
서로 다른 두 점이 주어질 때마다 그 두 점을 union 함수를 이용하여 합치고, 만일 그 두 점의 root가 같으면 사이클이 생긴 것이므로 탐색을 종료한다.

전체 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parents = [i for i in range(n)] #[0,1,2,3,4,5]
endgame = 0

def find(x):
    # x가 root가 아니라면 재귀로 root를 다시 찾고 갱신한다.
    if x != parents[x]:
        parents[x] = find(parents[x])
        return parents[x]
	# x가 root라면 그대로 반환
    if x == parents[x]:
        return x

def union(x, y, i):
    global endgame
    # root 찾기
    x = find(x)
    y = find(y)
    # 서로 다른 그룹이라면, 사이클이 안 만들어졌다면
    if x != y:
        # 트리를 합친다.
        parents[max(x,y)] = min(x,y)
    elif endgame == 0:
        endgame = i

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

print(endgame)