(백준 1238번 파티) 라이님 블로그 대회 알고리즘 따라잡기 16) 다익스트(Dijkstra's Algorithm)

최단거리 알고리즘 복습 1탄 - 다익스트라 알고리즘

 

백준 1238번

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

 

풀이에 중복이 있어 제거하는 풀이를 chatgpt에게 부탁했는데, 두번째 풀이도 바로 챗gpt 풀이다.(gpt가 틀렸길래 디버깅 좀 했쑴ㅎㅎ)

 

첫번째 풀이

다익스트라 알고리즘을 사용해서 all node -> X로 가는 최단 경로를 구한 후(N-1번의 다익스트라 알고리즘 사용) X -> all node로 가는 최단 경로를 구했다.(1번의 다익스트라 알고리즘 사용)

 

다익스트라 함수를 구현하는데 있어 겹치는 부분이 많아 아쉬운 풀이

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;
typedef pair<int, int> P;

int dijkstra(int N, int start, int end, const vector<vector<P>>& adj) {
	priority_queue<P, vector<P>, greater<P>> pq;
	vector<int> dist(N, INT_MAX);

	dist[start] = 0;
	pq.emplace(0, start);

	while (!pq.empty()) {
		int curr_dist = pq.top().first;
		int curr = pq.top().second;
		pq.pop();
		if (dist[curr] < curr_dist) continue;

		for (const P& edge : adj[curr]) {
			int next = edge.first;
			int weight = edge.second;


			if (dist[next] > dist[curr] + weight) {
				dist[next] = dist[curr] + weight;
				pq.emplace(dist[next], next);
			}
		}
	}

	return dist[end];
}

int dijkstra_max(int N, int start, const vector<vector<P>>& adj, vector<int> NtoX) {
	priority_queue<P, vector<P>, greater<P>> pq;
	vector<int> dist(N, INT_MAX);

	dist[start] = 0;

	pq.emplace(0, start);

	while (!pq.empty()) {
		int curr_dist = pq.top().first;
		int curr = pq.top().second;
		pq.pop();
		if (dist[curr] < curr_dist) continue;

		for (const P& edge : adj[curr]) {
			int next = edge.first;
			int weight = edge.second;


			if (dist[next] > dist[curr] + weight) {
				dist[next] = dist[curr] + weight;
				pq.emplace(dist[next], next);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		dist[i] = dist[i] + NtoX[i];
	}

	dist[start] = 0;

	return *max_element(dist.begin(), dist.end());
}

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

	int N, M, X; cin >> N >> M >> X;
	vector<vector<P>> adj;
	adj.resize(N);

	for (int i = 0; i < M; i++) {
		int s, e, w; cin >> s >> e >> w;
		adj[s - 1].emplace_back(e - 1, w);
	}

	// 각 node -> X로 가는 최단거리
	vector<int> NodeToX(N);
	vector<int> Temp(N); Temp = { 0 };
	for (int i = 0; i < N; i++) {
		if (i != X - 1) NodeToX[i] = dijkstra(N, i, X-1, adj);
	}

	// X -> 각 node + 각 node -> X로 가는 최대거리
	cout << dijkstra_max(N, X - 1, adj, NodeToX);

	return 0;	
}

 

두번째 풀이

정방향과 역방향 그래프를 동시에 저장하고 다익스트라 알고리즘을 사용하는 방식

다익스트라 알고리즘을 총 N번 사용한다는 점에서 첫번재 풀이와 동일하지만 역방향 그래프를 저장함으로써 다익스트라 함수를 재활용할 수 있다는 장점이 있다!

 

 vector<int> dist_from_X = dijkstra(N, X - 1, adj); 

: X(=start)에서 출발해서 각 노드에 도착하는 최단거리를 저장
 vector<int> dist_to_X = dijkstra(N, X - 1, reverse_adj);

: X(=end)에서 끝나는 최단거리를 저장

 

reverse_adj를 사용하는 순간 시작점이 끝점의 역할을 한다는 점이 상당한 Key!

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef pair<int, int> P;

vector<int> dijkstra(int N, int start, const vector<vector<P>>& adj) {
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<int> dist(N, INT_MAX);
    dist[start] = 0;
    pq.emplace(0, start);

    while (!pq.empty()) {
        int curr_dist = pq.top().first;
        int curr = pq.top().second;
        pq.pop();
        if (dist[curr] < curr_dist) continue;

        for (const P& edge : adj[curr]) {
            int next = edge.first, weight = edge.second;
            if (dist[next] > dist[curr] + weight) {
                dist[next] = dist[curr] + weight;
                pq.emplace(dist[next], next);
            }
        }
    }
    return dist;
}

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

    int N, M, X; cin >> N >> M >> X;
    vector<vector<P>> adj(N), reverse_adj(N);

    for (int i = 0; i < M; i++) {
        int s, e, w; cin >> s >> e >> w;
        adj[s - 1].emplace_back(e - 1, w);
        reverse_adj[e - 1].emplace_back(s - 1, w);
    }

    vector<int> dist_from_X = dijkstra(N, X - 1, adj);
    vector<int> dist_to_X = dijkstra(N, X - 1, reverse_adj);

    int max_round_trip_time = 0;
    for (int i = 0; i < N; i++) {
        if (i != X - 1) {
            int round_trip_time = dist_from_X[i] + dist_to_X[i];
            max_round_trip_time = max(max_round_trip_time, round_trip_time);
        }
    }

    cout << max_round_trip_time << "\n";
    return 0;
}