[BOJ][Python]1976 풀이

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

1976번: 여행 가자

import sys
ssr = sys.stdin.readline

def find(node):
    if uf[node] == node:
        return node
    else:
        uf[node] = find(uf[node])
        return uf[node]
    
def union(node1, node2):
    root1, root2 = find(node1), find(node2)
    if root1 != root2:
        if rank[root1] < rank[root2]:
            uf[root1] = root2
        elif rank[root1] == rank[root2]:
            uf[root1] = root2
            rank[root2] += 1
        else:
            uf[root2] = root1

n = int(ssr())
m = int(ssr())
uf = [i for i in range(n)]
rank = [0 for _ in range(n)]
for i in range(n):
    line = list(map(int, ssr().split()))
    for j in range(n):
        if line[j] == 1:
            union(i, j)
route = list(map(lambda x : int(x)-1, ssr().split()))
check = uf[find(route[0])]
for i in range(1, len(route)):
    if check != uf[find(route[i])]:
        print('NO')
        break
else:
    print('YES')

아무래도 유니온 파인드의 기본 문제들이다 보니까(정확히는 유니온 파인드를 써야 한다는 걸 미리 알았으니까) 쉽게 풀 수 있었던 문제가 아닌가 싶습니다. 유니온 파인드를 몰랐거나 어떤 알고리즘을 사용해서 풀어야 한다는 걸 몰랐다면 좀 더 헤맸겠죠.

 

해당 문제는 다른 도시를 경유하더라도 주어진 경로를 다 방문하기만 하면 되는 문제입니다. 경로에 방향성이 없기 때문에 어떻게든 연결만 되어있다면 즉, root 노드가 동일하다면 가능하다는 얘기죠(최소 횟수를 구하라든가 몇 번만에 간다든가 방향성이 있다든가 하는 조건이 없기 때문에 유니온 파인드를 쓰면 된다는 사실을 아는 순간 풀리는 문제나 다름 없습니다). 따라서 이 때 까지 해왔던 것처럼 유니온 파인드를 사용하시면 됩니다.