[Python] 백준 1976번 : 여행 가자

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

1976번: 여행 가자

---

💡 문제 풀이

그래프 이론 중 Union-Find 문제이다.

 

union 함수와 find 함수를 구현할 수 있다면 쉽게 풀 수 있다.

입력받은 값들에 대해서 각 node별로 연결해주고

여행 계획에 맞춰 find 함수를 사용해 1개의 값으로 귀결된다면 YES를, 아니라면 NO를 출력해주면 된다.

✔️ 느낀 점

union-find 알고리즘에 대해서 제대로 이해를 못 해서 낯설었던 문제였다. 새로운 알고리즘을 공부하는 좋은 계기가 되었다.

💻 코드

import sys
input = sys.stdin.readline

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

def union(x, y):
    x = find(x)
    y = find(y)
    
    parent[y] = x
    
N = int(input())
M = int(input())
parent = list(range(N+1))
for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j]: union(i, j+1)

plans = list(map(int, input().split()))
ans = set([find(p) for p in plans])

if len(ans) == 1: print('YES')
else: print('NO')