[ 백준 1976 ] 여행 가자 - Python

문제 보기

이 문제는 플로이드-워셜 문제이다.

 

여행이 가능한 지 확인하기 위해서는 모든 경로에 대한 정보가 필요하다.

플로이드-워셜을 사용하면 모든 도시 사이의 거리를 구할 수 있다.

 

플로이드-워셜 알고리즘은 3중 for문을 통해 쉽게 구현할 수 있다.

플로이드-워셜을 통해서 모든 도시 사이의 거리를 구한 후 여행을 하면서 만약 해당 지점에 도착할 수 없으면 NO를 출력하였다.

 

* 자기 자신에게 여행을 가는 경우도 있다!

 

코드

if __name__ == "__main__":
    n = int(input())  # 총 도시의 수
    m = int(input())  # 여행 계획에 속한 도시들의 수
    graph = [list(map(int, input().split())) for _ in range(n)]
    move = list(map(int, input().split()))

    # 플로이드-워셜 알고리즘을 통해 모든 노드 간의 최소 거리를 구한다.
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 0 and i != j:  # 길이 없다는 뜻
                graph[i][j] = 1e9  # 10억으로 대입

    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    # 여행 여부 확인
    flag = True
    pre_index = move[0] - 1
    for i in range(1, m):
        if graph[pre_index][move[i] - 1] >= 1e9:  # 길이 없는 경우
            flag = False
            break
        else:
            pre_index = move[i] - 1

    if flag:
        print("YES")
    else:
        print("NO")