풀이 아이디어

한 도시 건너서 연결된 도시를 플로이드-와셜 알고리즘으로 구한다.
city_info[i][j]가 i도시에서 j도시로 연결되었는지 보여준다면 (0=연결X, 1=연결O)
city_info[i][k]==1이고 city_info[k][j]==1이면
city_info[i][j]==1이라는 걸 보장하기 때문이다.

이행적 폐쇄 행렬

이행적 폐쇄 행렬이란?
그래프의 연결 여부를 0과 1로 표시하는 행렬이다.

3
3
0 1 0
1 0 1
0 1 0
1 2 3

위에 1976문제의 예제 입력도 그래프 노드 간의 연결을 0과1로 표현했다.
플로이드-와셜 알고리즘으로 한 도시를 거쳐 다른 도시로 연결되는 경우도 1로 표현했다.

풀이 코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
# 도시의 수
city_info = []
for _ in range(n):
    city_info.append(list(map(int,input().split())))

# 여행 갈 순서
plan = list(map(int,input().split()))

# 건너건너 연결된 도시를 찾기 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if city_info[i][k] and city_info[k][j]:
                city_info[i][j]=1

# 계획한 도시 순서대로 이동가능한지 확인하기 
can_visit = "YES"
start=plan[0]-1
for target in plan:
    next=target-1
    if start==next:
        continue
    if not city_info[start][next]:
        can_visit="NO"
    start=next
print(can_visit)