알고리즘 설계 실습 - 최적 경로 찾기

---

문제

n(2 ≤ n ≤ 100)개의 도시가 있습니다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있습니다. 각 버스는 한 번 사용할 때 필요한 비용이 있습니다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하세요.

 

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어집니다. 그리고 셋째 줄 부터 m+2줄까지 다음과 같은 버스의 정보가 주어집니다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어집니다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있습니다. 시작 도시와 도착 도시가 같은 경우는 없습니다. 비용은 100보다 작거나 같은 자연수입니다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있습니다.

 

출력

n개의 줄을 출력해야 합니다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최 소 비용입니다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력하세요.

 

입력 예시

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

---

풀이

floyd.py

import sys
import math

n = int(sys.stdin.readline())  # 도시의 수
m = int(sys.stdin.readline())  # 버스의 수

# 모든 최단 거리를 저장할 2차원 list
route = [[math.inf] * (n + 1) for _ in range(n + 1)]
# route 초기화
for i in range(n):
    for j in range(n):
        if i == j:
            route[i+1][j+1] = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    route[a][b] = min(c, route[a][b])   # 최소값 넣기 

#floyd 알고리즘
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            route[a][b] = min(route[a][b], route[a][k] + route[k][b])

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if (route[a][b] == math.inf) or a == b:
            print("0",  end=" ")
        else:
            if b == n:
                print(route[a][b])
            else:
                print(route[a][b], end=" ")

입력: 도시의 수(n)와 버스의 수(m)를 입력받습니다. 이 때 sys.stdin.readline() 함수를 사용해 입력을 받으므로, 이 코드는 주로 대회나 시험 환경에서 입력을 빠르게 받기 위해 사용된다. 

초기화: route라는 2차원 리스트를 만들어 모든 값에 math.inf(무한대)를 초기화합니다. 도시 자기 자신으로의 경로는 비용이 0이므로, 대각선을 0으로 설정한다. 

버스 정보 입력: 각 버스 노선에 대해 시작 도시 a, 도착 도시 b, 그리고 비용 c를 입력받는다. 이미 저장된 값보다 적은 비용의 노선이 입력될 경우, 해당 노선의 비용을 업데이트한다. 이 과정은 중복 노선에 대해 최소 비용만을 저장하기 위함이다. 

Floyd 알고리즘: 모든 도시 쌍에 대해 각 도시를 거쳐 가는 경로를 검사하며 최소 비용을 계산한다. 이중 반복문을 통해 모든 도시 a, b에 대하여 route[a][b]를 최소화한다. 이 때, 도시 k를 중간 경유지로 사용한다. 

결과 출력: 마지막으로, 계산된 최단 경로를 출력한다. 경로의 비용이 무한대(math.inf)인 경우, 도달할 수 없으므로 "0"을 출력한다. 그렇지 않은 경우 해당 비용을 출력한다. 이 때, 출력 포맷을 맞추기 위해 마지막 도시에 대해서는 줄바꿈을 추가하고, 그 외에는 공백을 사용한다.

---