최단경로 응용문제(이코테) - 2

날짜 : 2022. 12. 07

사용 언어 : python

 

문제

 

코드

import sys

INF = int(1e9)
n, m = map(int, sys.stdin.readline().split())  # 전체 회사의 개수, 경로의 개수
route = [[INF] * (n + 1) for i in range(n + 1)]

for i in range(1, n+1):
    route[i][i] = 0  # 본인노드

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    route[s][e] = 1
    route[e][s] = 1

a, b = map(int, sys.stdin.readline().split())  # 도착지, 거쳐갈 노드 (입력순서 주의)

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

total = route[1][b] + route[b][a]

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

 

 

풀이

- 플로이드-워셜 알고리즘을 활용하여 풀이한다.

 

 

알게된 점

- 풀이는 전반적으로 쉬웠지만 입력순서와 경유지, 도착지를 정확하게 이해하지 못해 많은 시간을 소요했다.

- k가 경유지인지, x가 경유지인지 정확하게 파악하지 못했고

- a, b를 맨 처음에 입력하는 바람에 엉뚱한 값이 계속 나왔다.

- 문제풀때 좀 더 신경쓰는 노력을 해야겠다.

 

 

참고 사이트

- https://youtu.be/acqm9mM1P6o