[이코테] 최단경로 문제 2 [미래도시] 파이썬 풀이

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(1000000)
import heapq

INF = int(1e9)
N,M = map(int,sys.stdin.readline().split())
graph = [[INF] *(N+1) for _ in range(N+1)]
for i in range(N+1):
    for j in range(N+1):
        if i == j:
            graph[i][j] = 0

for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a][b] = 1
    graph[b][a] = 1

X, K = map(int,sys.stdin.readline().split())
# K = 소개팅(경유) , X = 판매 목표

for p in range(1,N+1):
    for q in range(1,N+1):
        for r in range(1,N+1):
            graph[q][r] = min(graph[q][r],graph[q][p] + graph[p][r])
            graph[r][q] = min(graph[r][q],graph[r][p] + graph[p][q])
    
if (graph[1][K] + graph[K][X]) >= INF:
    print(-1)
else:
    print(graph[1][K] + graph[K][X])

M <= 100 인것을 이용하여 

다익스트라 알고리즘을 사용할 수도 있지만, 플로이드 - 워셜 알고리즘을 사용하는 것이 훨씬 간결한 방법이다.

현재 K(소개팅)을 경유하여 최종 목표는 X이므로 

최단 경로의 거리는 graph[1][K] + graph[K][X] 이런 식으로 해주면 된다.

3중 for문은 플로이드 - 워셜 알고리즘의 기본 소개이다.

 q-> r vs q->p->r 둘중 최소 경로를 갱신해주면서 

각 출발점으로부터 최단경로를 모두 갱신해줄 수 있다.

이후 최단 경로의 거리는 graph[1][K] + graph[K][X]

만약 이 거리가 INF보다 크다는 것은 1->K->X가 가능하지 않은 root이므로 -1을 출력.

도달 가능하다면 둘을 합친 것을 더해서 답을 구하였다.

플로이드 워셜 - 알고리즘의 시간복잡도: O(N^3) 

3중 for문을 본다면 직관적으로 와닿을 것이다.