[백준/C++] 11404번 : 플로이드 (DP 문제, 플로이드-워셜 알고리즘)

플로이드 

문제

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

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

예제 출력 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

---

해당 문제는 플로이드-워셜 알고리즘의 기본 유형 문제 중 하나이다.

알고리즘을 풀기에 앞서, 플로이드-워셜에 대한 이해가 많이 부족해서 학습 후 문제를 풀이하였다!

 

2023.07.26 - [💻코딩테스트] - [알고리즘] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

 

플로이드 워셜 알고리즘은 동적 계획법(DP)을 이용하여 풀이하기 때문에, 점화식을 세워 노드 간의 최소 비용을 구하였다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int Max_Cost = 10000000; // Max 설정값 주의하기

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n+1, vector<int>(n+1));
	fill(graph.begin(), graph.end(), vector<int>(n+1, Max_Cost)); // 1. 무한대 초기화

	for (int i = 1; i <= n; i++)
		graph[i][i] = 0; // 자기자신 경로 초기화

	for(int i = 0; i < m; i++)
	{
		int start, end, cost;
		cin >> start >> end >> cost;
		if(graph[start][end] > cost)
			graph[start][end] = cost;
	}

	for(int bridge = 1; bridge <= n; bridge++)
	{
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n ;j++)
			{
				if (i == j) continue;
				if (bridge == i || bridge == j) continue;

				graph[i][j] = min(graph[i][j], graph[i][bridge] + graph[bridge][j]);
			}
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if (graph[i][j] >= Max_Cost) // 문제 조건에 무한대인 경우 0으로 출력
				graph[i][j] = 0;

			cout << graph[i][j] << " ";
		}
		cout << '\n';
	}

	return 0;
}

 

풀이한 내용을 차례로 설명하자면 아래와 같다.

 

1. 노드의 개수 n + 1만큼의 2차원 배열을 선언하고, 무한대를 의미하는 큰 정수로 초기화한다.

이때, 처음에는 경로의 최대 비용이 100,000보다 작거나 같은 자연수라고 해서 2배정도인 200,000으로 무한대를 지정했었다.

 

근데 거쳐가는 경로 등을 연산하면서 경로 비용이 무한대로 설정한 정수(200,000)를 넘어가서 풀이가 계속 실패하였다...

(97%에서 감칠맛나게 계속 실패함)

다음에는 꼭 넉넉한 큰 자연수의 무한대 값으로 초기화하도록 하자.

 

2. 1번 노드가 1번 노드로 가거나, 2번 노드가 2번 노드로 가는것처럼 자기 자신으로 가는 경로의 비용은 0이므로, graph[i][i] = 0으로 초기화하였다.

 

3. 이후 입력받는 시작지점, 도착지점, 비용 값을 토대로 graph[start][end] 배열을 초기화하였다.

이때, 한 가지 생각해볼 점은 문제에 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라는 조건이 존재한다는 점이다.

따라서, 입력을 받을 때 기존에 저장된 값보다 작은 경우에만 경로비용을 새롭게 초기화할 수 있도록 조건문을 넣어주었다.

 

4. 플로이드 워셜 알고리즘의 핵심인 "거쳐가는 노드"를 의미하는 bridge = 1 ~ bridge = n 까지의 for문을 최상위 for문으로 돌고, 안에는 그래프 탐색을 위한 i = 1 ~ i = n, j = 1 ~ j = n의 2중 for문을 한번 더 돌았다.

 

이때, 실수로 거쳐가는 노드를 최상위 for문이 아닌 최하위 for문으로 작성한다면 해당 문제의 채점 결과가 실패로 처리된다.

 

그 이유는, 거쳐가는 정점을 기준으로 최단 경로를 계산하는 것이 아닌, 출발 정점과 도착 정점을 기준으로 최단 경로를 계산하게 되기 때문이다. 이렇게 되면 거쳐가는 정점 k를 고려하지 않은 상태에서 최단 경로를 결정하는 경우가 발생하므로 문제가 발생하게 된다.

 

i값과 j값이 변하지 않을 때에도 최하위로 놓은 k 루프 안에서 k값이 이동하면서 제대로 동작하지 않게 되는것이다.

 

거쳐가는 노드 K를 기준으로 검사	i -> j 경로를 기준으로 거쳐가는 노드 k를 검사

 

즉, 거쳐가는 노드 반복문이 하위인 경우에는 위 그림에서 오른쪽에 해당하는 결과가 나오게 되는 것이다. 

 

5. 모든 최소비용 거리 연산이 완료된 graph 배열을 순서대로 출력한다.

이때, 문제 조건에 따라 경로가 무한대인 경우에는 0으로 출력하도록 조건문을 넣어주었다.

---

https://www.acmicpc.net/problem/11404

11404번: 플로이드