[백준 1976번] 여행 가자

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

1976번: 여행 가자

2023.04.11 - [코딩 테스트/개념] - Union-Find

# 1 <= N <= 200
# 1 <= M <= 1000

import sys

readline = sys.stdin.readline

N = int(readline())
M = int(readline())

graph = []
for i in range(1, N + 1):
    row = list(map(int, readline().split()))

    for j in range(1, N + 1):
        if row[j - 1] == 0:
            continue
        graph.append((i, j))

union_find = [i for i in range(N + 1)]


def find(v):
    if union_find[v] == v:
        return v

    new_v = find(union_find[v])
    union_find[v] = new_v
    return new_v


def union(v1, v2):
    find_v1 = find(v1)
    find_v2 = find(v2)

    if find_v1 < find_v2:
        union_find[find_v2] = find_v1
    else:
        union_find[find_v1] = find_v2


for (v1, v2) in graph:
    union(v1, v2)

plans = list(map(int, readline().split()))
start = union_find[plans[0]]
is_possible = True
for i in range(1, M):
    if union_find[plans[i]] != start:
        is_possible = False
        break

print("YES" if is_possible else "NO")

처음 풀었을 때 9%에서 자꾸 틀려서 도대체 뭘까 생각했는데, union 함수에서 find_v1과 find_v2를 비교하는 기준이 없어서였다. 그냥 find_v2과 find_v2가 다를때 union_find[find_v2] = union_find[find_v1]으로 했더니 틀렸다. 

반례는 찾지 못했는데, 뭔가 대표 노드가 엇갈리는 부분이 있을 것 같다는 느낌이 든다. 어쨌든 union 정의 자체가 비교해서 상위 노드를 대표 노드로 하는 거니까 저렇게 풀어야 겠다