[BOJ 1238 // C++] 파티

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1238번 문제인 파티이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1238

1238번: 파티

이 문제에서는 각 지점에서 X까지 각각의 최단거리와 X에서 각 지점까지 각각의 최단거리를 구해야한다.

그러므로 처음에는 다익스트라(dijkstra) 알고리즘을 각 시작점과 종료점을 지정해 한번씩 돌리는 코드를 작성해보았고, 이 코드는 무리없이 통과되었다. 아래는 먼저 제출한 코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;
using std::vector;
using std::pair;

vector<pair<int, int>> G[1001];

int main()
{
    int N, M, X;
    cin >> N >> M >> X;
    for (int i = 0;i < M;i++) {
        int s, e, w;
        cin >> s >> e >> w;
        G[s].push_back(pair<int, int> {e, w});
    }
    int ans = 0;
    for (int i = 1;i <= N;i++) {
        if (i == X) continue;
        int totaldist = 0;
        priority_queue<pair<int, int>> pq;
        int dist[1001];
        for (int j = 1;j <= N;j++) dist[j] = 1000001;
        bool done[1001];
        for (int j = 1;j <= N;j++) done[j] = false;
        dist[i] = 0;
        pq.push({ 0,i });
        while (!pq.empty()) {
            int current = pq.top().second; pq.pop();
            if (done[current]) continue;
            else if (current == X) break;
            done[current] = true;
            for (auto edge : G[current]) {
                int endnode = edge.first;
                int weight = edge.second;
                if (dist[endnode] > dist[current] + weight) {
                    dist[endnode] = dist[current] + weight;
                    pq.push({ -dist[endnode],endnode });
                }
            }
        }
        totaldist += dist[X];
        priority_queue<pair<int, int>> pq2;
        for (int j = 1;j <= N;j++) dist[j] = 0;
        for (int j = 1;j <= N;j++) done[j] = false;
        for (int j = 1;j <= N;j++) dist[j] = 1000001;
        dist[X] = 0;
        pq2.push({ 0,X });
        while (!pq2.empty()) {
            int current = pq2.top().second; pq2.pop();
            if (done[current]) continue;
            else if (current == i) break;
            done[current] = true;
            for (auto edge : G[current]) {
                int endnode = edge.first;
                int weight = edge.second;
                if (dist[endnode] > dist[current] + weight) {
                    dist[endnode] = dist[current] + weight;
                    pq2.push({ -dist[endnode],endnode });
                }
            }
        }
        totaldist += dist[i];
        if (totaldist > ans) ans = totaldist;
    }
    cout << ans;

    return 0;
}

그러나, 채점 목록을 보니 위 코드(84ms)보다 빨리 문제를 해결한 사람들이 많이 눈에 띄었다. 그래서 조금 더 관찰을 하다 다음과 같은 특징을 발견할 수 있었다.

 

1) 다익스트라 알고리즘은 (중간에 중단하지 않는다면) 한번의 실행으로 한 점에서 다른 모든 점으로 가는 최단경로를 한번에 구할 수 있다. 이를 굳이 위의 코드에서처럼 각 점의 경우 다시 실행해서 반복할 이유는 없다.

2) 마찬가지로, 모든 다른 점에서 정해진 한 점으로 오는 최단경로는 모든 간선(edge)의 방향을 반대로 한 그래프에서 다익스트라 알고리즘을 이용하면 똑같이 구할 수 있다.

 

따라서, 총 두번의 다익스트라 알고리즘의 이용으로 "모든 점에서 한 점으로의 각각의 최단경로의 길이"와 "한 점에서 모든 점으로의 각각의 최단경로의 길이"를 전부 구할 수 있다.

이를 구현하는 코드를 제출하였더니 사용된 시간을 많이 줄일 수 있었다. (4ms)

 

아래는 나중에 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;
using std::vector;
using std::pair;

vector<pair<int, int>> G1[1001];
vector<pair<int, int>> G2[1001];
int roundtrip[1001]; // 왕복 거리의 합을 저장할 배열

int main()
{
    int N, M, X;
    cin >> N >> M >> X;

    for (int i = 0;i < M;i++) {
        int s, e, w;
        cin >> s >> e >> w;
        G1[s].push_back(pair<int, int> {e, w}); // 원래 방향 그래프
        G2[e].push_back(pair<int, int> {s, w}); // 반대 방향 그래프
    }
    int ans = 0;
    priority_queue<pair<int, int>> pq; // Dijkstra 1 (X에서 각 점으로의 최단거리)
    int dist[1001];
    for (int i = 1;i <= N;i++) dist[i] = 1000001;
    bool done[1001];
    for (int i = 1;i <= N;i++) done[i] = false;
    dist[X] = 0;
    pq.push({ 0,X });
    while (!pq.empty()) {
        int current = pq.top().second; pq.pop();
        if (done[current]) continue;
        done[current] = true;
        for (auto edge : G1[current]) {
            int endnode = edge.first;
            int weight = edge.second;
            if (dist[endnode] > dist[current] + weight) {
                dist[endnode] = dist[current] + weight;
                pq.push({ -dist[endnode],endnode });
            }
        }
    }
    
    for (int i = 1;i <= N;i++) roundtrip[i] += dist[i];

    priority_queue<pair<int, int>> pq2; // Dijkstra 2 (각 점에서 X로의 최단거리)
    for (int i = 1;i <= N;i++) dist[i] = 1000001;
    for (int i = 1;i <= N;i++) done[i] = false;
    dist[X] = 0;
    pq2.push({ 0,X });
    while (!pq2.empty()) {
        int current = pq2.top().second; pq2.pop();
        if (done[current]) continue;
        done[current] = true;
        for (auto edge : G2[current]) {
            int endnode = edge.first;
            int weight = edge.second;
            if (dist[endnode] > dist[current] + weight) {
                dist[endnode] = dist[current] + weight;
                pq2.push({ -dist[endnode],endnode });
            }
        }
    }
    for (int i = 1;i <= N;i++) {
        roundtrip[i] += dist[i];
        if (ans < roundtrip[i]) ans = roundtrip[i]; // 두 방향의 걸리는 시간의 합이 최대인 경우를 찾는다
    }

    cout << ans;

    return 0;
}