[이코테] 최단 경로 - 플로이드

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 백준 링크에도 수록되어 있으므로 링크를 참조하자.

https://www.acmicpc.net/problem/11404

11404번: 플로이드

사고과정

• 전형적은 플로이드-워셜 알고리즘 문제이긴 한데, 특이한 점이 있었다. 시작 노드 -> 도착 노드간의 간선이 비용만 다르게 중복해서 나올 수 있다는 점! 처음에 이부분을 놓치고 들어가서 다시 돌아왔다. 입력 받을때 그리디 방식을 활용해서 해결함.
• INF 값으로 설정한 거리 테이블 초기값을 마지막에 특정 도시 -> 특정 도시 갈 수 없는 경우를 0으로 바꾸어주는 로직이 추가되야 함.
• 그런데, 백준에서 테스트 케이스를 제출했을 때, 마지막 출력문에서 자꾸 틀렸다고 나왔다. graph[a][b] == INF 일때, graph[a][b] = 0으로 업데이트해주고 출력해주는 걸로 했는데 그랬다. 그래서 이를 바꿔서 graph[a][b] == INF 일때 그냥 0으로 바로 출력해주고, 나머지 따로 출력해주는 것으로 해서 통과되긴 했는데, 이유를 모르겠다. 그래서 여기에다가 질문해놓은 상태..

풀이

import sys

n = int(input())
m = int(input())
INF = int(1e9)
graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1):
    graph[a][a] = 0

# 주어진 시작,도착 도시, 비용 graph에 반영 -> 시작->도착 도시 연결하는 노선 여러개일 수 있음에 주의!
for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a][b] = min(graph[a][b], cost)

# 거쳐가는 노드 k로 탐색하면서 플로이드워셜 알고리즘 수행
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])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print(0, end=' ')
        else:
            print(graph[a][b], end=' ')
    print()