[python] 1976 - 여행 가자

1976번: 여행 가자 (acmicpc.net)

1976번: 여행 가자

 

union-find를 활용하는 문제였다.

도시를 탐색하면 되었기 때문에 bfs나 dfs로도 탐색할 수 있을 것 같았는데

유니온 파인드를 최근에 공부하였기 때문에

이를 이용하여 문제를 해결하였다.

 

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n = int(input())
m = int(input())

parent = [i for i in range(n+1)]
rst=True

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

def union(a,b):
    a = find(a)
    b = find(b)
    
    if a < b :
        parent[b] = a 
    else:
        parent[a] = b 
        
for i in range(n):
    cityList = list(map(int, input().split()))
    
    for j in range(len(cityList)):
        city = i+1
        idx = j+1
        if i != j and cityList[j] == 1:
            union(city, idx)

plan = list(map(int, input().split()))

root = parent[plan[0]]
for i in range(len(plan)):
    x=plan[i]
    if root != parent[x]:
        rst = False
        break

if rst == False:
    print("NO")
else:
    print("YES")

 

도시는 여러번 방문 가능하고 여행 계획을 가려면 도시가 연결되어 있어야 하므로

여행을 계획한 도시들의 루트노드가 모두 같다면 여행이 가능하며

그렇지 않다면 도시가 연결되어 있지 않으므로 여행이 불가능하다.