미래 도시(PS)

출처:: M기업 코딩 테스트

분류:: 플루이드 워셜 알고리즘 

 

1. 문제 이해 및 해결과정

- N의 범위가 100이하로 매우 한정적이므로 플로이드 와셜알고리즘 이용

 

2. 풀이방법

#미래도시
import sys
from queue import PriorityQueue

INF = int(1e9) #10억

#노드의 개수 및 간선의 개수를 입력받기
n,m=map(int,input().split())

graph = [[INF]*(n) for _ in range(n)]

for i in range(m):
    X, Y = map(int, input().split())
    graph[X-1][Y-1] = 1
    graph[Y-1][X-1] = 1

#비용은 0으로 초기화
for i in range(n):
    graph[i][i] = 0

X, K = map(int, input().split())

# N 은 100이하로 한정적이므로 플로이드와셜알고리즘 이용하면 된다.
for i in range(n):
    for j in range(n):
        for k in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
                
result = graph[0][K-1] + graph[K-1][X-1]
if result < INF:
    print(result)
else:
    print(-1)

 

해설 )

이 문제의 핵심 아이디어는 1번 노드에서 X를 거쳐 K로가는 최던거리는 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리)라는 점이다.