[백준] 1976번 - 여행 가자

---

문제 분석

도시의 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다.
즉 입력으로 주어진 값들이 서로 연결되어 있는지를 파악하는 과정을 통해 문제를 해결할 수 있다.

---

소스 코드

# 여행 가자

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
M = int(input())
arr = [0] * (N + 1)
success = True

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

def find(idx):
    if idx == arr[idx]:
        return idx
    else:
        arr[idx] = find(arr[idx])
        return arr[idx]

for i in range(N):
    routes = list(map(int, input().split()))
    for r in range(len(routes)):
        if routes[r] == 1:
            arr[find(r + 1)] = arr[find(i + 1)]

schedule = list(map(int, input().split()))
before = schedule[0]
for route in schedule[1:]:
    if find(before) != find(route):
        success = False
        break
    before = route

if success:
    print("YES")
else: print("NO")