[python] 백준 11404 - 플로이드

출처 : 백준, https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

# n개의 도시 사이를 운행하는 m개의 버스가 있음
# A B C -> A 도시에서 B 도시로 가는 비용 C
# 가격이 다른 동일 노선이 존재할 수 있음.

# 각 도시에서 다른 도시로 가는 최소 비용을 출력
    # 갈 수 없을 경우 0 출력

 

 

먼저, 생각해야 할 부분

 

1. 가격이 다른 동일 노선이 존재할 수 있다.

2. 모든 도시에서 모든 도시로 가는 최소 비용을 구해야한다. -> 플로이드-워셜 알고리즘

3. 갈 수 없을 경우 0을 출력해야한다.

4. 반복문을 통해 많은 입력을 받을 때, input() 함수는 느리다.

    시간 초과가 난다면 input() 함수를 사용한건 아닌지 고려해보자.

 

---

 

풀이

 

import sys

INF = float('inf')

def solution(n, cost_matrix):
    for k in range(n):
        for i in range(n):
            if i == k:
                continue

            for j in range(n):
                if i == j or j == k:
                    continue

                prev_val = cost_matrix[i][j]
                next_val = cost_matrix[i][k] + cost_matrix[k][j]

                cost_matrix[i][j] = min(prev_val, next_val)

    for line in cost_matrix:
        for num in line:
            print(num if num != INF else 0, end=' ')
        print()

n = int(input())
bus = int(input())

cost_matrix = [[INF for j in range(n)] for i in range(n)]

for _ in range(bus):
    A, B, cost = map(int, sys.stdin.readline().rstrip().split())

    cost_matrix[A - 1][B - 1] = min(cost, cost_matrix[A - 1][B - 1])

solution(n, cost_matrix)

 

---

시간 복잡도

O(N^3)

 

알게 된 점

 

플로이드-워셜 알고리즘

 

모든 점으로부터 모든 점으로의 최단 거리를 구할 때는 플로이드-워셜 알고리즘을 사용한다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들