<aside> 🔥 백준 11404번 문제

</aside>

<aside> 🔥 문제 정리

n개의 도시와 m개의 버스가 있다.

버스는 a → b로 가는 비용이 있다.

a → b 로 가는데 필요한 비용의 최소값을 구하는 프로그램을 작성하라.

입력 조건
첫째줄 : 도시의 개수 n
둘째줄 : 버스의 개수 m
셋째줄 ~ m + 2 : 시작 도시, 도착 도시, 비용

# 입력
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

# 출력
0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

</aside>

<aside> 🔥 접근 방법

기본적인 플로이드 워셜 알고리즘을 이용하면 최단거리 테이블을 작성할 수 있을 것 같다.

점화식 $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$을 적용해서 코드를 작성해보았다.

</aside>

<aside> 🔥 코드 진행

입력값은 텍스트 파일로 분리해 실행했다.

n (도시의 개수)와 m(버스의 개수)를 입력 받아서 거리 테이블을 생성해준다.

import sys

with open('플로이드_텍스트.txt') as f:
    INF = int(1e9)
    sys.stdin = f
    input = sys.stdin.readline

    n = int(input()) # 노드의 개수
    m = int(input()) # 간선의 개수

    # 거리 테이블 생성
    dist = [[INF] * (n + 1) for _ in range(n + 1)]

자기 자신에게 가는 경로는 0으로 설정해준다.

for i in range(1, n + 1):
    dist[i][i] = 0

시작점, 도착점, 비용을 입력받아 테이블에 비용을 업데이트해준다.

for _ in range(m):
        a, b, c = map(int, input().split())
        if c < dist[a][b]:
            dist[a][b] = c

점화식 D_{ab} = min(D_{ab}, D_{ak} + D_{kb})을 사용해서 경로를 통해 가는것을 비교한다.

for k in range(1, n + 1):
  for a in range(1, n + 1):
      for b in range(1, n + 1):
          dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

문제에서 갈 수 없는곳은 0으로 처리하도록 해서 아래와 같이 작성한다.

for row in dist[1:]:
      print(" ".join([str(el) if el != INF else '0' for el in row[1:]]))

</aside>