사실 본인은 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)