백준 20040번 사이클 게임 | python | find-union

문제

링크

풀이

사실 본인은 union-find 문제 유형임을 알고 풀이에 들어갔지만, 그럼에도 한 번에 아이디어를 못 떠올렸다 🥲

문제를 읽다보면 자연스레 서로소 집합구조 문제란 것은 쉽게 알아차릴 수 있긴하다. (여기서 플레이어 순서는 풀이할때 전혀 상관하지 않아도 됨) 그래서 서로소 집합을 찾기만 하면 답이 나오려나 싶었는데, 사이클을 만든다는 것은 서로소 집합을 구성하는 것과는 또 다른 문제라고 생각해서 .. 조금 꼬아서 생각했던것 같다.

예를 들어 예제 입력과 같이 0 1 1 2 2 3 5 4 0 4 가 주어진다고 하였을 때 union-find 연산을 통해 서로소 집합을 구해보면 모든 원소가 동일한 집합인데, 사이클은 아니다. 아래와 같이 표현되기 때문이다.

그렇다면 동일 집합을 넘어서 사이클 형태려면 어떤 아이디어가 추가되어야할까?

💡 두 노드 간의 부모 루트가 '같은 지'를 먼저 확인함으로써 이미 같은 집합에 들어온 노드 인지를 파악하면 된다

for c in range(m):
    a, b = map(int, input().split())
    parent_a = find_parent(parent, a)
    parent_b = find_parent(parent, b)
    if parent_a == parent_b:
        if answer == 0:
            answer = c + 1
    else:
        # union 작업 수행 코드

두 노드간의 부모 루트가 같다는 것은 이미 서로가 같은 집합에 존재한다는 것인데 한 번 더 union-find를 진행하게 되면 사이클이 형성된다는 것을 생각해낼 수 있다.

아래는 전체 코드이다.

import sys

input = sys.stdin.readline

n, m = map(int, input().strip().split())

parent = [i for i in range(n)]


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


answer = 0
for c in range(m):
    a, b = map(int, input().split())
    parent_a = find_parent(parent, a)
    parent_b = find_parent(parent, b)
    if parent_a == parent_b:
        if answer == 0:
            answer = c + 1
    else:
        # union작업
        if parent_a < parent_b:
            parent[parent_b] = parent_a
        else:
            parent[parent_a] = parent_b

print(answer)