[Python/Baekjoon] B1976. 여행가자

💬 문제

문제 난이도: 골드 4

문제 링크: https://www.acmicpc.net/problem/1976

문제 설명

도시들의 개수, 도시들 간 연결 여부가 주어진다.
그리고 도시를 여행할 순서가 주어졌을 때, 해당 순서로 도시를 여행할 수 있는지를 판별하라.

문제조건
1. a도시와 b도시가 연결되어 있다 == b도시와 a도시가 연결되어 있다.
2. a->b로 여행을 갈 때, a와 b를 직접적으로 잇는 연결이 없더라도 다른 도시 c를 통해서 갈 수 있다면(a-c-b), 여행 갈 수 있다.
3. 같은 도시를 여러 번 방문해도 된다.
4. 도시의 개수는 200 이하이다.

❗️접근 방법

코드(Kruskal)

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
parents = [i for i in range(N+1)]

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

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

for i in range(N):
    arr = list(map(int, input().split(' ')))
    for j in range(i+1, N):
        if arr[j] == 1: # --- 1️⃣: 두 도시 (i+1, j+1)이 연결되어 있으므로 
            union(i+1, j+1)

plans = list(map(int, input().split(' ')))

def solution():
    for i in range(M-1):
        if find(plans[i]) != find(plans[i+1]):
            return 'NO'
    return 'YES'

print(solution())