백준11404 - 플로이드 (플로이드 워셸) Python

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

해당 문제는 모든 도시에서, 각 모든 도시로 가야할 때의 최소비용을 요구하는 문제다.

따라서 지난 포스팅에서 언급한 플로이드-워셸 알고리즘을 활용하여 해결할 수 있다.

2023.11.22 - [개발/algorithm] - 프로그래머스 - Lv.3 순위 (플로이드-워셸) Python

 

문제에서 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다와 만약 갈 수 없는 경우 0을 출력하라는 주의 사항만 유의하면 된다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  cities = int(data.pop(0))
  data.pop(0)
  
  arr = [list(map(int, v.split())) for v in data]
  graph = [[float('inf')] * cities for _ in range(cities)]
  
  for i in range(cities) :
    graph[i][i] = 0
  
  for s,e,w in arr : 
    # 동일한 시작도시 & 도착도시의 간선이 주어질 수 있으므로, 비교해서 최저값으로 저장
    graph[s-1][e-1] = min(graph[s-1][e-1], w)
   
  # 플로이드 워셸
  for i in range(cities) :
    for j in range(cities) :
      for k in range(cities) :
        graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])
  
  print('\n'.join(map(lambda x : ' '.join(map(lambda y : str(y) if y != float('inf') else '0', x)), graph)))
  
solution(input_data)