Q41. 여행 계획

문제 참고

[이코테] 그래프 알고리즘 - 여행 계획 (tistory.com)

[이코테] 그래프 알고리즘 - 여행 계획

 

 

여행 계획에 있는 여행지가 이어져있는지만 확인하면 되고 이는 union-find에서 계획 속 각 여행지들이 같은 집합에 속하지는지만 확인하면 되는 문제다.

 

#풀이에서는 여행지 넘버가 0부터 시작된다고 가정했다. 편하게 구현하려고.

N, M = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

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

parent = [i for i in range(N)]

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

def union(parent, x, y):
    px = find(parent, x)
    py = find(parent, y)

    if px < py:
        parent[py] = px
    else:
        parent[px] = py

for i in range(N):
    for j in range(N):
        if j < i:
            continue
        if graph[i][j] == 1:
            union(parent, i, j)
        
root = find(parent, plan[0])
for i in range(1, M):
    if find(parent, plan[i]) != root:
        print("NO")
        exit(0)
print("YES")