문제

BOJ 11404: 플로이드 https://www.acmicpc.net/problem/11404

풀이

조건

• n(2 ≤ n ≤ 100)개의 도시가 있다.(시간제한 : 1초)
  • 시간복잡도가 O(N^3)인 플로이드-워셜 알고리즘을 사용할 수 있다.
• 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구한다.
• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
• 시작 도시와 도착 도시가 같은 경우는 없다.

풀이 순서

• n(2 ≤ n ≤ 100)개의 도시가 있다.(시간제한 : 1초)
  • 시간복잡도가 O(N^3)인 플로이드-워셜 알고리즘을 사용할 수 있다.
• 처음에는 모든 위치로 가는 데 INF의 시간이 걸린다고 해놓는다.
  • graph : 한 도시에서 다른 도시로 가는 비용을 기록할 2차원 배열
• graph에서 자기 자신은 0시간만에 가는 것으로 간주한다.
• 한 도시에서 다른 도시로 가는 버스가 여러대 일 수 있다는 조건이 있어 입력받을 때 그 중 가장 비용이 작은 값이 저장되도록 한다.

코드

Python

import sys

INF = int(1e9)

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

# 처음에는 모든 위치로 가는 데 INF의 시간이 걸린다고 해놓음
graph = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
# 자기 자신은 0시간만에 가는 것으로 간주함
for i in range(1, n + 1):
    graph[i][i] = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    # 버스가 여러개 일 수 있어서 그 중 가장 비용이 적은 값이 들어가게 함
    graph[a][b] = min(graph[a][b], c)

# 플로이드-워셜 알고리즘
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] != INF:
            print(graph[i][j], end=' ')
        else:
            print(0, end=' ')
    print()

정리

• 한 도시에서 다른 도시로 가는 버스가 여러개 일 수 있다는 조건을 놓쳤었다.
• 출력 형식에 실수를 했었다.