백준 1976: 여행 가자 (Python)

 

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

1976번: 여행 가자

 

문제의 해결법은 쉽게 생각해낼 수 있었다.

입력된 여행 계획의 도시들이 서로 연결되어 있는지만 확인하면 된다.

 

도시들의 연결 정보를 입력받을 때 1이면 union해준다.

 

계획을 입력받은 후 시간을 줄이기 위해 리스트에서 중복 원소를 제거해주고

find를 통해 모두 같은 부모를 가지고 있는지(= 하나의 집합인지) 확인해주면 된다.

 

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


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

parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i

cities = []
for i in range(n):
    cities.append(list(map(int, input().split())))
    for j in range(n):
        if cities[i][j] == 1:
            union_parent(parent, i+1, j+1)


plan = list(map(int, input().split()))
plan_set = set(plan) # 중복 제거

check = find_parent(parent, plan[0])
for i in plan_set:
    if find_parent(parent, i) != check:
        print("NO")
        exit(0)
print("YES")