미래 도시

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

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

 

1. 문제 이해 및 해결과정

- N의 범위가 100이하로 매우 한정적 

 

2. 풀이방법

 1. 플루이드 워셜

#미래도시
#
import sys
sys.stdin = open("input.txt","r")
INF = int(1e9) #10억

#노드의 개수 및 간선의 개수를 입력받기
n,m=map(int,input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]

#비용은 0으로 초기화
for a in range(1,n+1):
    for b in range(1,n+1):
        if a==b:
            graph[a][b]=0

#간선 정보 입력받기
for _ in range(m):
    a,b=map(int,input().split())
    graph[a][b]=graph[b][a]=1

#거쳐 갈 노드 x와 최종 목적지 k입력
x,k=map(int,input().split())

#점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])

#수행된 결과를 출력
distance = graph[1][k] + graph[k][x]

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

 

3. 오답원인

 

4. 알게된 점