[백준 1976번] 여행 가자 - python

문제 링크

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

1976번: 여행 가자

 

풀이

- 유니온 파인드 알고리즘 사용해서 풀이

- path에 있는 도시들이 하나의 그래프에 속해있다면 여행 경로로 가능하다는 뜻 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline 

# find 함수 : 부모 찾기 
def find(a):
    if a != parent[a]:
        p = find(parent[a])
        parent[a] = p
    return parent[a]

# union 함수 : 두 노드 합치기 
def union(a,b):
    a = find(a)
    b = find(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
n = int(input())
m = int(input())

graph = []

# 부모 테이블 
parent = [0] * n

# 부모를 자기 자신으로 초기화 
for i in range(n):
    parent[i] = i
    
for i in range(n):
    graph.append(list(map(int,input().split())))
    for j in range(n):
    	# 두 도시가 연결되어 있으면 두 도시 합치기 
        if graph[i][j] == 1 :
            union(i,j)
    
# 경로 체크
parent = [-1] + parent

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

# 시작 도시의 부모 
start = parent[path[0]]

for i in range(1,m):
	# 같은 그래프에 속하지 않으면 
    if parent[path[i]] != start:
        print("NO")
        break
else:
    print("YES")