[baekjoon 1238] 파티 (플로이드와샬, 다익스트라) (C++)

www.acmicpc.net/problem/1238

1238번: 파티

각 집(N)마다 목표점까지 왕복하는 최단 거리 중 가장 큰 값을 찾는 문제이다.

 

처음에 각 노드 당 최단거리를 구하는 것이기 때문에 플로이드 와샬 알고리즘을 생각했지만, N이 1000으로 O(N^3)의 시간 복잡도를 가지는 플로이드 와샬로 풀리지 않을 것으로 생각했다.

결론적으로는 통과됐다. (왜지?)

 

플로이드로 풀고, 더 좋은 방법이 없을까 하고 찾아봤더니 다익스트라를 이용해서 풀 수 있는 문제였다.

물론 다익스트라를 모든 점에서 해서 모든 점마다의 최단거리를 구한 후 결과를 도출하는 것은 그리 효율적이지 못하다.

 

생각을 해보면, 값을 입력받을 때 단방향의 가중치값을 입력받는다. (1 -> 2는 3, 1 -> 3은 4)

그리고 1번에서 다익스트라를 실행하면 1번에서 2~N까지의 점까지의 최단 거리를 구하는 것이다.

 

여기서, 정방향으로 입력받은 것을 반대로 역방향으로 바꾼 뒤 다익스트라를 실행시키면 어떻게 될까?

 

바로 각 점에서 1번까지의 최단거리가 구해지는 것이다.

 

정방향 : 특정 노드에서 나머지 노드까지의 최단 거리

역방향 : 각 나머지 노드들에서 특정 노드까지의 최단 거리가 되는 셈이다.

 

애초에 입력값의 조건이 X에서 Y로 가는 길이 있고 Y에서 X로 돌아오는 길이 주어진다고 하였으니 길은 뚫려있지만 방향 간 가중치가 다른 것이기 때문에 역방향 값을 이용해서 돌려주면 단 두 번만에 최단 거리를 구할 수 있게 된다.

 

1. 통과한 플로이드 와샬 풀이

그냥 매번 풀듯이 3중 FOR문을 이용해서 풀었다.

각 거리를 갱신해준 뒤, i -> 목표 + 목표 -> i 가 가장 큰 것을 구해주었다.

#include <iostream>
#include <algorithm>

#define INF 987654321
using namespace std;

int n, m, arr[1001][1001], from, to, weight, target;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> target;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				continue;
			else
				arr[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		cin >> from >> to >> weight;
		arr[from][to] = weight;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
			}
		}
	}

	int mx = 0;

	for (int i = 1; i <= n; i++) {
		mx = max(mx, arr[i][target] + arr[target][i]);
	}
	cout << mx;
}

 

2. 다익스트라 두 번 이용해서 푸는 풀이

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define INF 987654321
using namespace std;


int n, m, dist[1001], from, to, weight, target, result[1001];
vector<vector<pair<int,int>>> v1, v2;

void dijkstra(int startX, vector<vector<pair<int, int>>> v) {
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[startX] = 0;
	priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(make_pair(0, startX));

	while (!pq.empty()) {
		int totalDistance = pq.top().first;
		int x = pq.top().second;
		pq.pop();

		for (int i = 0; i < v[x].size(); i++) {
			int distance = v[x][i].first;
			int nx = v[x][i].second;

			if (dist[nx] > totalDistance + distance) {
				dist[nx] = totalDistance + distance;
				pq.push(make_pair(dist[nx], nx));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		result[i] += dist[i];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> target;

	v1.resize(n + 1);
	v2.resize(n + 2);

	for (int i = 0; i < m; i++) {
		cin >> from >> to >> weight;
		v1[from].push_back(make_pair(weight, to));
		v2[to].push_back(make_pair(weight, from));
	}

	dijkstra(target, v1);
	dijkstra(target, v2);

	int mn = 0;

	for (int i = 1; i <= n; i++) {
		mn = max(mn, result[i]);
	}
	cout << mn;
}

함수 파라미터로 vector <pair <int, int>> v [1001]을 넘기는 것이 되지 않았고, 따라서 vector <vector <pair <int, int>>>로 정의하고 resize 해주어서 넘겨주었다.

왕복거리를 구해야 하는 것이므로, 다익스트라를 한 번 수행하고 왕복 값을 저장해두는 result배열에 저장해주었다.

 

확실히 시간 차이가 많이 나긴 한다.

위가 다익스트라 2번, 밑이 플로이드이다.