이번 문제는 유니온-파인드 알고리즘을 통해 해결하였다. 처음에는 플로이드-와샬을 통해 접근하였지만 80%에서 오답처리 되었고, 다른 사람들의 풀이를 참고한 결과 모두 유니온-파인드로 풀이한다는 사실을 알게 되었다. 유니온-파인드를 통해 각 도시들의 루트를 찾고, 계획을 순회하며 처음 도시와 방문할 다른 도시들의 루트가 모두 같다면, 즉 같은 부분집합에 속한다면 YES를 출력하고, 그렇지 않다면 NO를 출력하는 방식으로 해결하였다.

Code

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b
def find(a):
    if a != parents[a]:
        parents[a] = find(parents[a])
    return parents[a]
n = int(input())
m = int(input())
parents = [i for i in range(n)]
path = [[]]
for i in range(n):
    tmp = list(map(int, input().split()))
    for j in range(n):
        if tmp[j] == 1:
            union(i, j)
parents = [-1] + parents
plan = list(map(int, input().split()))
start = parents[plan[0]]
for i in range(1, m):
    if parents[plan[i]] != start:
        print('NO')
        break
else:
    print('YES')