[09-04 최단 경로] 미래도시

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에 있는 문제이다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

문제는 책 안에 있다!!

나는 이 문제에 접근하기 위해 고민을 했었지만, 책이 너무 깔끔하게 푼 것 같아서 쭉 따라해봤다. 

 

import sys
input = sys.stdin.readline

INF = int(1e9)
n,m = map(int,input().split())
graph = [[INF]*(n+1) for i in range(n+1)]

for i in range(1,n+1):
    graph[i][i] = 0

for i in range(m):
    a,b = map(int,input().split())
    graph[a][b] = 1
    graph[b][a] = 1

x,k = map(int,input().split())

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

distance = graph[1][k] + graph[k][x]

if distance >= INF :
    print(-1)
else :
    print(distance)