[G4] 백준 11404 - 플로이드 (Python3)

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

11404번: 플로이드

---

해결방법

플로이드-워셜 알고리즘을 이용해 풀이했다.

풀이👀

이번 입력은 [출발-도착-비용]이 들어오는데, 출발과 도착 정보가 동일한 입력도 포함된다. 그래서 이런 경우를 대비해주어야 한다. 이 문제는 모든 경로로 이동하는 최소비용 정보를 (출력하라고)요구하고 있다. 그러므로 출발과 도착 정보가 동일하게 주어질 땐 기존 입력값과 비교해서 더 작은 값을 반영해서 이 문제를 풀면 된다.

---

코드🐱‍👓

INF = 10 ** 8

n = int(input())
m = int(input())
graph = [[INF]*n for _ in range(n)]

for a in range(n):
    for b in range(n):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    # 출발 노드, 도착 노드, (출발->도착)비용
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = min(graph[a-1][b-1], c)

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

for a in range(n):
    for b in range(n):
        print(0 if (k:=cost[a][b]) == INF else k, end=' ')
    print()

코드 설명

for _ in range(m):
    # 출발 노드, 도착 노드, (출발->도착)비용
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = min(graph[a-1][b-1], c)

 

위 코드가 풀이에서 말했던 부분이다. graph는 모든 원소가 cost보다 항상 큰 정수 INF로 초기화되어 있는 상태이기 때문에 출발-도착-비용 정보가 입력되면, 당연히 비용이 올바르게 업데이트 될 것이고, 만약 출발-도착 정보가 같으나 비용이 다른 입력이 주어진다해도 그중에 더 작은 값만 반영해서 이 문제를 풀이할 수 있다. 그래서 올바른 정답을 출력할 수 있는 것이다.

---

 

 

포스트에 기재된 코드는 649B 코드에서 출력부분만 바다코끼리 연산자가 들어가도록 수정했습니다.