[백준/Python] 11404번 - 플로이드

문제

백준 11404번 - 플로이드

해결 과정

1. bus: 버스의 정보를 담는 2차 배열, 가장 큰 값 1e9로 초기화

2. 버스 정보를 입력받는다.
   c가 이미 있는 버스 정보의 비용 보다 작다면 c를 넣는다.

3. 시작 도시와 도착 도시가 같을 수 없으니까 0으로

4. 플로이드 워셜
   원래 있던 버스 비용과 k를 지나서 갔을 때 비용을 비교해서 작은 값을 넣는다.

5. 출력
   i에서 j로 갈 수 없을 경우에는 값이 입력 된 것이 아닌 것
   = 초기값인 INF인 것 = 그 자리에는 0을 출력
   그 외에는 띄어쓰기를 하며 출력

시행착오

• 왜 -> i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력을 고려하지 않았다 -> 출력하는 부분 수정

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

INF = int(1e9)
bus = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(m):
  a, b, c = map(int, sys.stdin.readline().split())
  # 이미 같이 들어있다면 둘 중 작은 값을 넣는다.
  if bus[a][b] != 0:
    bus[a][b] = min(bus[a][b],c)
  else:
    bus[a][b] = c
# 시작 
for i in range(n + 1):
    for j in range(n + 1):
        if i == j:
            bus[i][j] = 0

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

for i in range(1,n+1):
  print(*bus[i][1:])
 

풀이

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

INF = int(1e9)
bus = [[INF] * n for _ in range(n)]

for i in range(m):
  a, b, c = map(int, sys.stdin.readline().split())
  if bus[a-1][b-1] > c:
    bus[a-1][b-1] = c
  
for i in range(n):
  for j in range(n):
    if i == j:
      bus[i][j] = 0

for k in range(n):
  for i in range(n):
    for j in range(n):
      if i != j:
        bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j])

for i in range(n):
  for j in range(n):
    if bus[i][j] == INF:
      print(0, end=" ")
    else:
      print(bus[i][j],end=" ")
  print()