[ BOJ 백준 1238번 - 파티 ] 해설 및 코드

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

 

목적

각자 마을에서 X로 모였다가 다시 자기 마을로 돌아가는 최단 거리를 구하고, 그중 최대값을 구하자.

 

접근법

1. 다익스트라 알고리즘을 활용할 수 있는지 묻는 문제이다. X에서 각자 마을로 가는 최단 거리는 흔히 알고있는 다익스트라 알고리즘으로 구할 수 있다. (One to All)

 

2. 그러나 다익스트라 알고리즘을 이용해서 각자 마을에서 X로 가는 최단 거리를 구하기 위해서는 같은 다른 형식의 그래프가 필요하다. 바로 출발지와 목적지를 바꾼 형태의 그래프이다. (All to One)

 

3. 결국, 다익스트라 알고리즘에서 거리의 초기화 값을 0으로 주는 주체가, 출발지냐 목적지냐에 따라 구해지는 최단 거리 배열은 One to All과 All to One으로 나뉜다.

 

4. 플로이드 와샬로 AC를 받아낼 수 있지만, O(V^3)인 10^9(N의 최대값이 1000이므로)의 시간 복잡도를 가진 알고리즘이므로 해답으론 적절하지 않다.

 

#include<bits/stdc++.h>
#define LEN 1001
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int INF = 1e5;
 
struct Edge {
    int v, w;
    bool operator<(const Edge& oth)const { return w > oth.w; }
};
 
int* dijkstra(vector<Edge>* g, int n, int x) {
    int* d = new int[LEN];
    f(i, 1, n)d[i] = INF; d[x] = 0;
    priority_queue<Edge> q; q.push({ x,0 });
 
    while (!q.empty()) {
        int v = q.top().v, w = q.top().w; q.pop();
        if (d[v] != w)continue;
 
        for (Edge& edge : g[v]) {
            int tmp = d[v] + edge.w;
            if (d[edge.v] > tmp) {
                d[edge.v] = tmp;
                q.push({ edge.v,tmp });
            }
        }
    }
 
    return d;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, x; cin >> n >> m >> x;
    vector<Edge> g[LEN];
    vector<Edge> rg[LEN];
    while (m--) {
        int s, e, t; cin >> s >> e >> t;
        g[s].push_back({ e,t });
        rg[e].push_back({ s,t });
    }
    int* d = dijkstra(g, n, x), * rd = dijkstra(rg, n, x), ans = 0;
    f(i, 1, n) {
        int tmp = d[i] + rd[i];
        if (ans < tmp)ans = tmp;
    }
    cout << ans;
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.