[알고리즘] 백준 1238번: 파티 (C++)

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

1238번: 파티

두 개의 다익스트라 알고리즘을 선언하여 문제를 풀 수 있었다.

우선 문제를 두 개로 나누어 생각할 수 있다.

1) 갈 때 시간

2) 돌아올 때 시간

3) 두 값 합한 것 중 최댓값 도출

---

1) 갈 때 시간

갈 때의 시간은 여러 노드들로부터 다익스트라를 돌려봤다.

그리고 X까지 가는 데에 드는 비용들을 배열에 저장해두었다.

for (int i = 1; i <= N; i++) {
	dist2INFinit();
	dijkstra2(i);
	goX[i] = dist2[X];
}

---

2) 돌아올 때 시간

이때는 약간의 아이디어가 필요하다. 돌아올 때는 X에서부터 출발이므로 다익스트라(X)를 한 번 해주면 각 노드의 최소 비용이 돌아오는 시간이 된다.

 

dijkstra(X);

---

3) 두 값 합한 것 중 최댓값 도출

돌아올 때 혹은 갈 때 중에 거리가 INF가 있으면 갈 수 없거나 돌아올 수 없거나 중에 하나이기 때문에 continue 시킨다.

int maxValue = 0;
for (int i = 1; i <= N; i++) {
	if (dist[i] == INF || goX[i] == INF) continue;
	maxValue = max(maxValue, dist[i] + goX[i]);
}

---

[AC 코드]

갈 때의 시간을 구할 때 다익스트라를 여러 번 사용했어서 더 줄일 수 있는 방법이 있지 않을까 궁금증이 생겼었다.

왜냐하면 저렇게 여러 번 다익스트라를 돌리면 우선순위 큐를 사용한 다익스트라더라도 시간 복잡도가 O(N * E * logN)이 되게 되는데 Worst Case가 30,000,000이 될 수 있다. 하마터면 시간 초과가 날 수도 있는 코드였다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <cmath>
#define MAX 1001
#define INF 987654321
using namespace std;

int N, M, X;
vector<pair<int, int>> graph[MAX];
int dist[MAX];
int dist2[MAX];
int goX[MAX];

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

void dijkstra(int stop) { // 돌아올 때
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(stop, 0));
	dist[stop] = 0;
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if (dist[now] < cost) {
			continue;
		}
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(next, dist[next]));
			}
		}
	}
}

void dijkstra2(int node) { // 갈 때
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(node, 0));
	dist2[node] = 0;
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if (dist2[now] < cost) {
			continue;
		}
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist2[next]) {
				dist2[next] = cost + nextCost;
				pq.push(make_pair(next, dist2[next]));
			}
		}
	}
}

void dist2INFinit() {
	for (int i = 1; i <= N; i++) {
		dist2[i] = INF;
	}
	return;
}

int main() {
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}

	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}

	dijkstra(X);

	for (int i = 1; i <= N; i++) {
		dist2INFinit();
		dijkstra2(i);
		goX[i] = dist2[X];
	}

	int maxValue = 0;
	for (int i = 1; i <= N; i++) {
		if (dist[i] == INF || goX[i] == INF) continue;
		maxValue = max(maxValue, dist[i] + goX[i]);
	}

	cout << maxValue;
	return 0;
}