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을 출력한다.
예제 입력
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 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풀이
아래의 알고리즘 분류와 같이 그래프와 플로이드 워셜 알고리즘을 사용해 해결할 수 있다.
플로이드 워셜 알고리즘
그래프의 모든 간선에 대하여 가능한 모든 경로를 비교하는 알고리즘 이다.
플로이드 워셜 알고리즘의 시간복잡도는 V개의 간선에 대하여 이다.
두 개의 정점간의 최단 경로를 최적이 될 때 까지 개선해 최단 경로를 찾는 알고리즘이다.
입력 받기
표준 입출력 함수인 input을 사용하지 않고 sys을 import해 사용하였다.
저장할 수 있는 가장 큰 정수를 저장하기 위해 INF변수를 선언하고 sys.maxsize를 저장했다.
크기의 그래프를 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()결과
자료구조를 배운지 그렇게 오랜 시간이 지나지 않았음에도 기억이 잘 나지 않았다.
다시 리마인드하는 겸해서 포스팅과 함께 문제를 풀어보았다.
기본적인 플로이드 워셜 알고리즘을 이용해 해결할 수 있는 문제였다.
✅ 코드는 [여기]에서 확인할 수 있다.
