백준 - 1976번(유니온 파인드, 재귀)

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

1976번: 여행 가자

import sys
sys.setrecursionlimit(200000)

def find(a):
    if a == arr[a]:
        return a
    x = find(arr[a])
    arr[a] = x
    return arr[a]

def union(a,b):
    a = find(a)
    b = find(b)
    if a == b:
        return
    arr[max(a,b)] = arr[min(a,b)]


n = int(sys.stdin.readline())

arr = [0]

for i in range(1,n+1):
    arr.append(i)
visited = [False for _ in range(n+1)]

m = int(sys.stdin.readline())

for i in range(1,n+1):
    ord = list(map(int,sys.stdin.readline().split()))

    for j in range(n):
        if ord[j] == 1:
            union(i,j+1)

dest = list(map(int,sys.stdin.readline().split()))

k = find(dest.pop())

for i in dest:
    if k != find(i):
        print('NO')
        exit(0)

print('YES')

유니온 파인드 문제다.

유니온 연산을 모두 수행해준다.

후에 방문해야 하는 출발 지점의 부모 노드를 find로 찾아주고 모두 동일하면 YES 아니면 NO를 출력해준다.

union과 find 함수만 구현할 줄 알고 이 문제가 유니온 파인드를 사용해서 푸는 문제라는 걸 파악하는 게 중요하다.