[solved.ac 골드4] 11404_플로이드 (파이썬, 플로이드-와샬)

제한 사항

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

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

예제

---

나의 풀이

플로이드-와샬 알고리즘에 대해 알고있다면 굉장히 쉬운 문제였다. (심지어 문제 제목에서 어떤 알고리즘인지도 알려주는...)

골드4라서 응용이 있을 줄 알았는데 그냥 플로이드-와샬 알고리즘 그 자체이다.

 

플로이드-와샬 알고리즘 간단 설명

플로이드-와샬 알고리즘은 그래프 탐색 알고리즘이다.

그래프에 여러 노드가 존재할 때 특정 한 노드에서 다른 노드까지 이동하는 비용을 구할 때 사용하는데 이런 비슷한 알고리즘인 다익스트라 알고리즘과 약간 차이가 있다

다익스트라 알고리즘

• 시작 노드 a에서 나머지 노드까지 가는 비용을 계산할 때 사용한다.
• a가 아닌 b 노드에서 다른 노드까지의 최소 거리를 구하려면 b 노드를 시작으로 하는 다익스트라 알고리즘을 새로 돌려야한다.

플로이드-와샬 알고리즘

• 특정 노드에서 다른 특정 노드까지의 최소 비용을 모두 계산한다
• a에서 나머지 노드로 가는 비용과 b에서 나머지 노드로 가는 비용 등 모든 노드에 대해 알 수 있다.

어떤 문제에 어떤 알고리즘이 적합할까?

• 탐색의 시작 점이 주어지는 경우 : 다익스트라 알고리즘
• 모든 노드를 시작점으로 가질 수 있는 경우 : 플로이드-와샬 알고리즘

 

따라서 이 문제는 플로이드-와샬 알고리즘이 적합하다.

전체 코드

import sys
input = sys.stdin.readline

INF = 10 ** 9
n, m = int(input()), int(input())
bus = [[INF] * (n + 1) for _ in range(n + 1)] # INF로 초기화
# 노선 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    bus[a][b] = min(bus[a][b], c) # a -> b 비용 중 최소 비용 저장
# 플로이드-와샬
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
 			# i -> j 비용과 i -> k -> j 비용 중 더 싼 비용 선택
            if i != j: bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j])
for b in bus[1:]: # 0번 인덱스 제외
    for cost in b[1:]: # 0번 인덱스 제외
    	# INF라면 갈 수 없는 곳
        print(cost, end=' ') if cost != INF else print("0", end=' ')
    print()

채점 결과

코드는 완전히 동일하다.

밑의 코드는 Python3, 위의 코드는 PyPy3이다. 역시 반복 작업이 많은 풀이라 PyPy3가 빠르지만 그만큼 메모리도 더 많이 사용한다.