[백준]11404(파이썬) - 플로이드

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

11404번: 플로이드

 

• 이 문제는 제목을 읽으면 바로 떠오르는 풀이법이 하나 있죠. 바로 플로이드 워셜입니다.
• 플로이드 워셜은 다익스트라 알고리즘과 함께 최단거리를 계산하는 문제의 풀이법으로 유명한데요, 혹시 처음 들어보신분들은 아래 게시물을 한 번 읽고오시면 도움이 될 것 같습니다.

다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap))

 

• 이 문제는 먼저 힙을 사용한 다익스트라보단 플로이드 워셜이 효율적입니다. 이유를 말씀드리겠습니다.
  
  문제에서 요구하는 건 i에서 j로 가는데 필요한 최소 비용을 구해야 합니다. 처음 시작점을 주고 시작점에서 j까지 가는 최소 비용을 모두구하는 문제가 아니죠.
  
  후자의 경우 힙을 이용한 다익스트라 구현이 맞지만, 이 문제에서 다익스트라를 사용하면 모든 i에서 다익스트라를 한번씩 해줘야하기
  때문에 비효율적입니다. 따라서 이 문제는 i에서 j로 구하는 최소 비용을 n개 만큼 모두 구할 수 있는 플로이드 워셜이 효율적이죠.
  
  
• 추가적으로 예제 출력을 보면 2차원 배열로 되어 있는데 저는 출력 형식을 보고 플로이드 워셜을 이용한 구현이라고 확실을 가졌습니다.
• 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

 

import sys

# 도시의개수
n = int(input())
# 버스의 개수
m = int(input())
INF = 987654321
# 최소비용을 구하기 위한 문제이기 때문에
# INF로 초기화 해주고 갱신해준다.
graph = [[INF] *n for i in range(n)]
# print(graph)

# 시작 도시와 도착 도시를 연결하는 노선은 여러개다
# 이중에 최소비용만 담고 있으면 되기 때문에 갱신이 필요하다.
for _ in range(m):
    start,end,dis = map(int,input().split())
    # 가장 짧은거만 판단하면 되는거아닌가..? 작은걸로 갱신해서 값 넣어주기
    if graph[start-1][end-1] > dis:
        graph[start-1][end-1] = dis

# 플로이드 워셜 구현
# j에서 k로 갈 때 i를 거쳐서 가는경우와 바로 가는 경우를 비교해서
# 더 작은 값을 갱신해준다.
for i in range(n):
    for j in range(n):
        for k in range(n):
                if graph[j][k] > graph[j][i]  + graph[i][k] and  j != k:
                    graph[j][k]  = graph[j][i]  + graph[i][k]
         
# 만약 INF가 담겨있다면 방문을 하지 않은 것이기 때문에 0으로 바꿔준다.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 987654321:
            graph[i][j] =0

# 출력
for i in range(n):
    print(*graph[i])