방과후
ALGORITHM NOTE약 2분

BOJ 1238 - 파티

파티하러 가는 것도 힘드넹

#algorithm#boj#gold#dijkstra#graph-theory#shortest-path
아카이브로 돌아가기

문제 링크

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 NN명의 학생이 X (1≤X≤N)X\ (1 \le X \le N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 MM개의 단방향 도로들이 있고 ii번째 길을 지나는데 Ti(1≤Ti≤100)T_i(1 \le T_i \le 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1≤N≤1,000)N(1 \le N \le 1{,}000), M(1≤M≤10,000)M(1 \le M \le 10{,}000), XX가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1M+1번째 줄까지 ii번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 TiT_i가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 AA에서 다른 도시 BB로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

풀이

각 학생의 왕복 시간은 집 -> X 최단 거리와 X -> 집 최단 거리의 합이다. 이를 학생마다 따로 다익스트라로 구하면 비효율적이므로, 그래프를 정방향과 역방향으로 나눠 두 번만 다익스트라를 돌리면 된다.

코드에서는 vec[0]에 원래 방향 그래프를 저장해 X에서 각 마을로 돌아가는 최단 거리를 구하고, vec[1]에는 간선을 반대로 저장해 각 마을에서 X로 오는 최단 거리를 한 번에 계산한다. 역방향 그래프에서 X에서 출발하는 최단 거리는 원래 그래프에서 각 정점이 X까지 가는 최단 거리와 같다.

두 번의 다익스트라가 끝나면 각 학생 i에 대해 dist[0][i] + dist[1][i]를 계산하고, 그중 최댓값을 고르면 된다. 왕복을 각각 따로 구하는 대신 방향을 뒤집어 한 번에 계산하는 것이 핵심이다.

코드

cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
const int MAXN = 1001;
const int inf = 987654321;
int dist[2][MAXN];
 
//vec[0] : x에서 각 마을로 돌아가는데 사용
//vec[1] : 각 마을에서 x로 모이는데 사용
vector<pair<int, int>> vec[2][MAXN];
 
void dijkstra(int num, int x) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({x, 0});
 
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = pq.top().second;
		pq.pop();
 
		if (cost > dist[num][cur])
			continue;
 
		for (int i = 0; i < vec[num][cur].size(); i++) {
			int next = vec[num][cur][i].first;
			int nextCost = cost + vec[num][cur][i].second;
 
			if (nextCost < dist[num][next]) {
				dist[num][next] = nextCost;
				pq.push({next, nextCost});
			}
		}
	}
}
 
void solve() {
	int n, m, x, a, b, t;
	//a : 시작점, b : 끝점, t : 소요시간
	cin >> n >> m >> x;
 
	for (int i = 1; i <= n; i++) {
		dist[0][i] = inf;
		dist[1][i] = inf;
	}
 
	dist[0][x] = 0;
	dist[1][x] = 0;
 
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> t;
		vec[0][a].push_back({b, t});
		vec[1][b].push_back({a, t});
	}
 
	dijkstra(0, x);
	dijkstra(1, x);
 
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (dist[0][i] != inf && dist[1][i] != inf)
			ans = max(dist[0][i] + dist[1][i], ans);
	}
		
	cout << ans << '\n';
}
 
int main() {
    
    ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도

  • 시간 복잡도: 두 번의 다익스트라로 O((N+M)log⁡N)O((N + M) \log N)
  • 공간 복잡도: O(N+M)O(N + M)

마무리

왕복 최단 거리 문제는 정방향과 역방향 그래프를 같이 보면 훨씬 쉬워진다. 다익스트라를 두 번만 돌려도 모든 학생의 왕복 시간을 한꺼번에 계산할 수 있다.