[백준] 플로이드

최동혁·2022년 12월 6일

baekjoon python 알고리즘

백준

목록 보기

46/68

플로이드

solved_ac[Class4][플로이드](https://www.acmicpc.net/problem/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을 출력한다.

예제 입력 1

예제 출력 1

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

문제 해석

본 문제는 제목에서 나와있듯이 플로이드 워셜 알고리즘을 이용하여 푸는 문제이다. 다익스트라와 비슷한 계열이지만 다익스트라는 한 노드에서 갈 수 있는 노드들의 최단 거리를 계산하는 것이고, 플로이드는 여러 노드들끼리 갈 수 있는 최단 거리를 계산해주는 알고리즘이다. 그래서인지 다익스트라는 시간복잡도가 O(ElogV)인데 플로이드는 O(logn^3)이다. for문을 3번쓴다.

플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
- 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.

점화식

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인
- a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
점화식은 다음과 같다.

[초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화

[Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신

[Step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

[Step 3] 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

[Step 4] 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

예제 코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

INF = 10**9

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0
            
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    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:
            graph[i][j] = 0
        print(graph[i][j], end = " ")
    print()

풀이

위의 플로이드 와샬 예제 코드와 거의 비슷하다.
하지만 함정이 있는데, 위의 코드는 한 노드에서 다른 노드까지의 비용은 하나만 있다고 가정을 하였는데, 위 문제에서는 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 라고 되어있다. 그렇다는 뜻은 입력값을 위의 코드대로 넣는다면 최소 비용이 아닌 값이 업데이트가 되어서 원하는 답이 안나올 수도 있다. 그렇기 때문에 입력 받은 거리 비용이 전에 저장되어 있던 값보다 작아야만 업데이트가 되게끔 설계를 해줘야 한다.

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

INF = 10**9

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0
            
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    if graph[a][b] > c:
        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:
            graph[i][j] = 0
        print(graph[i][j], end = " ")
    print()