[백준 / C++] 1238번: 파티

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

1238번: 파티

난이도: solved.ac 골드 3

 

 

알고리즘 분류

그래프 이론, 데이크스트라 (Dijkstra)

 

접근 방법

(풀이 1)

먼저 각 노드 i에서 X로의 최단 거리를 파악하기 위해 모든 노드에 대해 다익스트라 알고리즘을 N번 사용한다.

그리고 dist[X]의 결과를 ans[i]에 저장한다.

그 다음 X에서 다른 모든 노드로의 최단 거리를 파악하는 X를 기준으로 한 다익스트라 알고리즘을 사용한다.

그리고 dist[i]의 결과를 ans[i]에 더해준다.

 

장점: 쉽게 떠올릴 수 있는 풀이다.

단점: 시간이 오래 걸린다.

 

(풀이 2)

- 다익스트라를 두 번만 사용하는 풀이-

 

그래프 정보를 입력받을 때 역방향으로 된 그래프를 추가로 저장한다.

Ex. 입력에서 u → v 로의 거리가 w라고 주어질 때

u에서 v로의 거리는 w라는 것을 저장하고,

v에서 u로의 거리가 w라는 것도 따로 저장한다.

 

즉, 그래프를 두 개 만들어서 하나는 정방향(문제에서 주어지는 원래 방향) 그래프, 다른 하나는 역방향 그래프로 사용한다.

 

그리고 역방향으로 저장한 그래프에서 X를 기준으로 다익스트라를 돌리고, 정방향으로 저장한 그래프에서 X를 기준으로 다익스트라를 돌린다.

 

역방향으로 저장한 그래프에서 X를 기준으로 한 다익스트라를 돌리고 나며 X에서 다른 노드로의 최단거리가 저장되게 된다.

이는 거꾸로 원래 그래프의 관점에서 생각해보면 다른 노드에서 X로의 최단 거리가 된다.

 

따라서 한 번의 다익스트라로 모든 노드에서 X로의 최단 거리를 구할 수 있다.

 

두 번의 다익스트라 결과를 더해서 합이 가장 큰 것을 골라주면 답이 된다.

 

장점: 시간이 매우 적게 든다.

단점: 아이디어를 떠올리기 어렵다.

코드

(풀이 1)

#include <bits/stdc++.h>
using namespace std;
#define INF (~0U>>2)
int N, M, X;
vector<int> dist;
int ans[1001];
vector<pair<int, int>> g[1001];
void dijkstra(int st);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> X;
	int a, b, c, i, j, max = 0;
	for (i = 0; i < M; i++) {
		cin >> a >> b >> c;
		g[a].push_back({ c,b });
	}
	for (i = 1; i <= N; i++) {
		if (i != X) {
			dijkstra(i);
			ans[i] += dist[X];
		}
	}
	dijkstra(X);
	for (i = 1; i <= N; i++) {
		ans[i] += dist[i];
		if (ans[i] > max)
			max = ans[i];
	}
	cout << max;
}

void dijkstra(int st) {
	dist.clear();
	dist.resize(N + 1, INF);
	dist[st] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,st });
	while (!pq.empty()) {
		int w = pq.top().first;
		int v = pq.top().second;
		pq.pop();
		if (w > dist[v])
			continue;
		for (int i = 0; i < g[v].size(); i++) {
			int nw = w + g[v][i].first;
			int nv = g[v][i].second;
			if (dist[nv] <= nw)
				continue;
			dist[nv] = nw;
			pq.push({ nw,nv });
		}
	}
}

 

(풀이 2)

#include <bits/stdc++.h>
using namespace std;
#define INF (~0U>>2)
int N, M, X;
vector<int> dist;
int ans[1001];
vector<pair<int, int>> g[1001][2];
void dijkstra(int st);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> X;
	int a, b, c, i, max = 0;
	for (i = 0; i < M; i++) {
		cin >> a >> b >> c;
		g[a][0].push_back({ c,b });	// 정방향
		g[b][1].push_back({ c,a });	// 역방향
	}
	dijkstra(1);	// 각 노드에서 X로 돌아오는 최단 거리
	dijkstra(0);	// X에서 각 노드로의 최단 거리
	for (i = 1; i <= N; i++) {
		if (ans[i] > max)
			max = ans[i];
	}
	cout << max;
}

void dijkstra(int k) {
	dist.clear();
	dist.resize(N + 1, INF);
	dist[X] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,X });
	while (!pq.empty()) {
		int w = pq.top().first;
		int v = pq.top().second;
		pq.pop();
		if (w > dist[v])
			continue;
		for (int i = 0; i < g[v][k].size(); i++) {
			int nw = w + g[v][k][i].first;
			int nv = g[v][k][i].second;
			if (dist[nv] <= nw)
				continue;
			dist[nv] = nw;
			pq.push({ nw,nv });
		}
	}
	for (int i = 1; i <= N; i++)
		ans[i] += dist[i];
}

 

성능

위: 풀이 1 / 아래: 풀이 2

풀이 1은 108ms의 성능을 보였고, 풀이 2는 0ms의 성능을 보였다.