BOJ 11404 플로이드

February 11, 2020

플로이드

시간 제한	메모리 제한
1초	256MB

문제

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

예제 출력

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

풀이

아래의 알고리즘 분류와 같이 그래프와 플로이드 워셜 알고리즘을 사용해 해결할 수 있다.

플로이드 워셜 알고리즘

그래프의 모든 간선에 대하여 가능한 모든 경로를 비교하는 알고리즘 이다.
플로이드 워셜 알고리즘의 시간복잡도는 V개의 간선에 대하여 $O(V^3)$ 이다.
두 개의 정점간의 최단 경로를 최적이 될 때 까지 개선해 최단 경로를 찾는 알고리즘이다.

입력 받기

표준 입출력 함수인 input을 사용하지 않고 sys을 import해 사용하였다.
저장할 수 있는 가장 큰 정수를 저장하기 위해 INF변수를 선언하고 sys.maxsize를 저장했다.
$N \times N$ 크기의 그래프를 INF의 값으로 초기화 한 후 정점과 간선 정보 입력을 받았다.
문제에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.라는 정보에 따라
min함수를 이용해 기존 값과 비교하여 더 적은 값을 해당 간선의 비용으로 저장하도록 했다.

import sys

input = sys.stdin.readline
INF = sys.maxsize

N = int(input())
M = int(input())
graph = [[INF for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())

    graph[a - 1][b - 1] = min(c, graph[a - 1][b - 1])

최소 비용 탐색

정점의 갯수만큼 3중 반복문을 진행한다.
일단 graph[i][i]즉 자기 자신에서 자신의 경로는 0이기 때문에 0으로 저장했다.
이미 저장되어 있는 비용과 정점 i를 거쳐서 정점 k로 가는 최솟값을 찾아 저장한다.

for i in range(N):
    graph[i][i] = 0

for i in range(N):
    for j in range(N):
        for k in range(N):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

최소 비용이 업데이트 되는 것을 출력해보면 아래와 같은 결과가 나온다.

1번 정점을 통하여 갈 수 있는 모든 경우의 최솟값

===================== Now i is 0 =====================
         0          2          3          1         10
2147483647          0 2147483647          2 2147483647
         8         10          0          1          1
2147483647 2147483647 2147483647          0          3
         7          4         10          8          0
================== Updated Completed ==================

2번 정점을 통하여 갈 수 있는 모든 경우의 최솟값

===================== Now i is 1 =====================
         0          2          3          1         10
2147483647          0 2147483647          2 2147483647
         8         10          0          1          1
2147483647 2147483647 2147483647          0          3
         7          4         10          6          0
================== Updated Completed ==================

3번 정점을 통하여 갈 수 있는 모든 경우의 최솟값

===================== Now i is 2 =====================
         0          2          3          1          4
2147483647          0 2147483647          2 2147483647
         8         10          0          1          1
2147483647 2147483647 2147483647          0          3
         7          4         10          6          0
================== Updated Completed ==================

4번 정점을 통하여 갈 수 있는 모든 경우의 최솟값

===================== Now i is 3 =====================
         0          2          3          1          4
2147483647          0 2147483647          2          5
         8         10          0          1          1
2147483647 2147483647 2147483647          0          3
         7          4         10          6          0
================== Updated Completed ==================

5번 정점을 통하여 갈 수 있는 모든 경우의 최솟값

===================== Now i is 4 =====================
         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
================== Updated Completed ==================

모든 정점에서 다른 모든 정점에서 방문할 수 있는 모든 최소 경로를 찾는 것을 볼 수 있다.

결과 출력

경로의 비용이 0이거나 INF인 경우 0을 출력하고
그렇지 않으면 graph[i][j]의 값을 그냥 출력해주면 되는 문제다.

for i in range(N):
    for j in range(N):
        if graph[i][j] == 0 or graph[i][j] == INF:
            print(0, end=" ")

        else:
            print(graph[i][j], end=" ")
    print()

코드 구현부

import sys

input = sys.stdin.readline
INF = sys.maxsize

N = int(input())
M = int(input())
graph = [[INF for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b, c = map(int, input().split())

    graph[a - 1][b - 1] = min(c, graph[a - 1][b - 1])

for i in range(N):
    graph[i][i] = 0

for i in range(N):
    for j in range(N):
        for k in range(N):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

for i in range(N):
    for j in range(N):
        if graph[i][j] == 0 or graph[i][j] == INF:
            print(0, end=" ")

        else:
            print(graph[i][j], end=" ")
    print()

결과

자료구조를 배운지 그렇게 오랜 시간이 지나지 않았음에도 기억이 잘 나지 않았다.
다시 리마인드하는 겸해서 포스팅과 함께 문제를 풀어보았다.
기본적인 플로이드 워셜 알고리즘을 이용해 해결할 수 있는 문제였다.

✅ 코드는 [여기]에서 확인할 수 있다.

Written by@Minsu Kim

Software Engineer at Devsisters Corp.