백준 1976 여행 가자 - 파이썬

 문제.

풀이.

https://turret1234.tistory.com/176

백준 1717 집합의 표현 - 파이썬

위 링크랑 풀이가 거의 유사하다. 입력 조건이 조금 다르지 푸는 알고리즘은 거의 똑같다.

연결된 집합끼리 유니온 연산을 해 주고 여행 계획인 도시끼리 파인드 연산을 해서 모두 같은 집합이라면 yes 아니면 no를 출력하면 된다.

 

소스코드.

import sys

# 유니온 (집합 합치기)
def union(a, b):
    a = find(a)
    b = find(b)

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

# 파인드 (루트 노드 찾기)
def find(target):
    if target == parent[target]:
        return target

    parent[target] = find(parent[target])
    return parent[target]

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n = int(input())
m = int(input())
parent = [i for i in range(n)]
isTrue = True
for i in range(n):
    check = list(map(int, input().split()))
    # union 연산
    for c in range(len(check)):
        if check[c] == 1:
            union(i, c)

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

# find 연산
for i in range(1, len(plan)):
    if find(plan[i-1]-1) != find(plan[i]-1):
        isTrue = False
        break

print('YES' if isTrue else 'NO')