[BOJ/백준 1719/C++] 택배

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

1719번: 택배

 

[문제 요약]

예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

 

이와 같은 경로표를 구하여라

 

[문제 조건]

- 첫째 줄에 두 수 n ( 1 ≤ n ≤ 200 ) 과 m ( 1 ≤ m ≤ 10000 ) 순서대로 주어진다.- n은 집하장의 개수, m은 집하장간 경로의 개수인 자연수이다.- 이어서 한 줄에 하나씩 집하장간 경로가 주어지는데, 두 집하장의 번호와 그 사이를 오가는데 필요한 시간이 순서대로 주어진다. 집하장의 번호들과 경로의 소요시간은 모두 1000이하의 자연수이다.

 

[문제 풀이]

처음에 표만 보고 최단거리 구하는 문제인가? 하고 생각했는데 아니였다.

 

위의 표를 설명해보자면 예를들어 1번에서 6번으로 가능 최단경로가 있다고 하면, 최단경로에서 1번 다음 노드가 2번 노드라는 의미다. 

 

그래서 어쨋든 최단거리를 구해야하는 문제이기 때문에 다익스트라 or 플로이드-와샬로 풀리는 문제다.

 

필자는 처음에 다익스트라로 접근하여 문제를 풀었는데 생각보다 시간이 오래걸려서 플로이드-와샬로도 풀어보았다.

 

먼저 다익스트라에 대한 설명은 이 링크를 참고하도록 하자. https://tobrother.tistory.com/6

[BOJ/백준 1238/C++] 파티

 

최단거리를 구한다고 해서 끝나는 문제가 아니다.

 

경로표를 어떻게 만들 것인가?

 

필자는 2차원 배열을 하나 더 만들어서 다익스트라를 진행하는동안 경로의길이 대한 값이 갱신될 때 경로표도 갱신되는 방식으로 작성하였다.

 

먼저 위의 그림을 예제로 1번 노드를 기준으로 초기상태를 나타내면 아래 그림과 같다.

 

과정을 그림 순서대로 나타내면 아래와 같다

1번과 연결된 2번 3번을 갱신시켜주고, 경로표에는 가장 처음에 진행했기 때문에 각자 번호를 저장.

 

다음에는 3번노드를 확인하고, 3번과 연결된 4,5,6번 노드를 갱신시키고, 경로표에는 3번기준에서 최단거리갱신이 일어난 번호만 경로표를 갱신 시켜준다.

다음은 2번 노드에서 확인해보면 5번 노드와 최단거리 갱신이 일어난다. 이때 경로표에도 2번으로 갱신한다.

 

이 과정을 계속해서 돌리면 1번노드 기준으로 아래와 같이 완성된다.

위 과정을 1번노드부터 N번 노드까지 수행한뒤 출력하면 정답이 된다.

 

[소스 코드1]

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <string>

using namespace std;

struct cmp {
	bool operator()(pair<int, int> a, pair<int, int> b)
	{
		return a.second > b.second;
	}
};

int N, M;
vector<vector<int>> dt1;
vector<vector<int>> dt2;
vector<vector<pair<int, int>>> edge;

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

	cin >> N >> M;
	dt1.resize(N + 1);
	edge.resize(N + 1);
	dt2.resize(N + 1);
	for (int i = 0; i < N + 1; i++) { dt1[i].resize(N + 1); dt2[i].resize(N + 1);}

	for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) { dt1[i][j] = 99999; dt2[i][j] = 99999; }

	int s, e, c;
	for (int i = 0; i < M; i++)
	{
		cin >> s >> e >> c;
		edge[s].push_back({ e ,c });
		edge[e].push_back({ s ,c });
	}

	for (int i = 1; i <= N; i++)
	{
		vector<bool> ck(N + 1);
		priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
		pq.push({i,0});

		while (!pq.empty())
		{
			pair<int, int> tmp = pq.top(); pq.pop();
			int node = tmp.first;
			int distance = tmp.second;

			ck[node] = true;

			for (int k = 0; k < edge[node].size(); k++)
			{
				int next_node = edge[node][k].first;
				int next_distance = edge[node][k].second;

				if (ck[next_node]) continue;

				int distance_sum = distance + next_distance;
				if (distance_sum < dt1[i][next_node])
				{
					if (dt2[i][node] == 99999)
					{
						dt2[i][next_node] = next_node;
					}
					else
					{
						dt2[i][next_node] = dt2[i][node];
					}
					dt1[i][next_node] = distance_sum;
					pq.push({ next_node, dt1[i][next_node] });
				}
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (dt2[i][j] == 99999) cout << "- ";
			else cout << dt2[i][j] << " ";
		}
		cout << "\n";
	}
}

 

 

 

다음으로는 플로이드-와샬로도 한번 풀어보도록 하자.

 

다익스트라는 하나의 정점에 대하여 다른 모든 정점으로의 최단거리를 구하는 알고리즘이라면, 플로이드-와샬은 모든 정점에서 모든 정점으로의 최단거리를 구한다.

 

그럼 다익스트라를 모든 정점에 대하여 돌리면 플로이드-와샬아닌가? 라고 생각했지만 동작 방식이 조금은 달랐다.

 

다익스트라는 가장 적은 비용을 갖는 정점을 하나씩 선택하여 구했다면, 플로이드-와샬은 거쳐가는 정점을 고정시키고 연산을 진행한다.

 

예제 그래프를 한번 그림으로 나타내보자

최단거리는 왼쪽 표와 같이 나타낼 수 있고, 경로표는 n,m 순서로 들어올때 dt2[n][m] = m, dt2[m][n] = n을 저장한 것이다.

 

그럼 플로이드 와샬을 적용해보자

 

플로이드-와샬의 방법은

(i 에서 j로 가는 최소비용 vs i에서 k까지 비용 + k에서 j까지 비용) 둘 중 작은 값을 저장하는 것이다.

즉 k를 거쳐서 가는 것이 더 빠르다면 최소비용을 갱신한다는 의미이다. (단, i,j,k중 두 개가 같으면 연산 x )

 

예를들어 dt[2][3]을 생각해보자, dt[2][3] = INF, dt[2][1] + dt[1][3] = 3 이기 때문에 dt[2][3]에는 최단거리가 3으로 갱신되고, 경로표에는 1을 거쳐가는 경우이기때문에 dt[2][3] 에는 dt[2][k] , k=1이기 때문에 1이 저장된다.

 

그림으로 나타내면

색칠된 부분을 제외한 영역에서 값이 갱신될 것이다.

 

노란색 부분이 k=1 일때 실제로 갱신된 값.

 

k = 2일때 주황색 영역을 제외한 곳에서 갱신이 일어나고, 실제로 바뀐 값은 노란색 영역

k를 6까지 수행하면 아래 그림과 같이 된다.

이 경로표를 그대로 출력하면 된다.

 

[소스 코드2]

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <string>

using namespace std;

int N, M;
vector<vector<int>> dt1;
vector<vector<int>> dt2;

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

	cin >> N >> M;
	dt1.resize(N + 1);
	dt2.resize(N + 1);
	for (int i = 0; i < N + 1; i++)
	{ 
		dt1[i].resize(N + 1); dt2[i].resize(N + 1);
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			dt1[i][j] = 99999;
			dt2[i][j] = 99999;
		}
	}

	int s, e, c;
	for (int i = 1; i <= M; i++)
	{
		cin >> s >> e >> c;
		dt1[s][e] = c; dt1[e][s] = c;
		dt2[s][e] = e;
		dt2[e][s] = s;
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (i == k || k == j || i == j) continue;
				if (dt1[i][k] + dt1[k][j] < dt1[i][j])
				{
					dt1[i][j] = dt1[i][k] + dt1[k][j];
					dt2[i][j] = dt2[i][k];
				}
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (dt2[i][j] == 99999) cout << "- ";
			else cout << dt2[i][j] << " ";
		}
		cout << "\n";
	}
}

 

굳