백준 - 1238. 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

풀이자체는 복잡한것이 없으리라 생각했다.

각 마을에서 목적지 까지 가는거리와 오는거리의 최소 길이를 구해야 하므로

다익스트라를 갈때, 올때 2번 호출해서 구하면 왕복 거리가 나오리라 생각했다.

그래서 나온것이 아래 코드다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
#define INF 2100000000
 
using namespace std;
 
class Node {
public:
    int index, time;
 
    Node(int index_, int time_) : index(index_), time(time_) {}
    Node(): Node(-1,-1){}
 
    bool operator <(const Node& rhs) const {
        return time > rhs.time;
    }
};
 
int N, M, X;
 
vector<vector<int>> nodes;        //nodes[a] : a에서 이동가능한 노드 번호의 목록
vector<vector<int>> weights;    //weights[a] : nodes[a] 와 대응되는 edge의 가중치
vector<int> dist;
 
//from에서 to까지 가는 최단경로의 길이
int Dijkstra(int start, int goal) {
    int ret = INF;
 
    priority_queue<Node> pq;
    pq.push(Node(start, 0));
 
    while (!pq.empty()) {
        Node cNode = pq.top();
        pq.pop();
 
        int from = cNode.index;
        int time = cNode.time;
 
        if (from == goal) {
            ret = min(ret, time);
            continue;
        }
 
        if (time > dist[from])
            continue;
 
        int cnt = nodes[from].size(); //현재 노드에서 이동가능한 노드의 갯수
        for (int i = 0; i < cnt; i++) {
            int to = nodes[from][i];
            int weight = weights[from][i];
 
            if (time + weight > dist[to])
                continue;
 
            dist[to] = time + weight;
            pq.push(Node(to, time + weight));
        }             
    }
 
    for (int i = 0; i < N; i++)
        dist[i] = INF;
 
    return ret;
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> X;
    X--;
    nodes.assign(N, vector<int>());
    weights.assign(N, vector<int>());
    dist.assign(N, INF);
 
    int from, to, weight;
    for (int i = 0; i < M; i++) {
        cin >> from >> to >> weight;
        from--, to--;
 
        nodes[from].push_back(to);
        weights[from].push_back(weight);
    }
 
 
    //int ret = Dijkstra(0, 1);
    int ret = -1;
    for (int i = 0; i < N; i++) {
        int a = Dijkstra(i, X);
        int b = Dijkstra(X, i);
 
        ret = max(ret, a + b);
    }
 
    cout << ret << endl;
 
    return 0;
}

76번째 X--;를 빼먹어서 디버깅에 약간 시간이 걸렸다.

정답은 나왔지만 성능이 매우 아쉽다.

0ms 속도가 나온 사람들이 굉장히 많은데 172ms의 속도가 나왔으며

똑같이 C++로 푼 사람들과 랭킹을 비교해도 중하위권이다.

 

성능개선 

다익스트라 알고리즘이 시작점에서 목적지 까지의 최단경로를 구하는 알고리즘이 아니라

하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘이라는 것이다.

즉, 모든 시작점에 대해 다익스트라 알고리즘을 한번씩 호출할 필요가 없다.

 

그러므로 X에서 각노드로 돌아와야 할 경우에는 X를 기준으로 다익스트라를 호출하면 모든 점으로 돌아가는 시작점을 얻을 수 있다.

하지만 각 노드에서 X로 가야하는 경우에는 어떻게 해야 할까?

간선의 방향을 뒤집고 다시한번 X를 시작점으로 모든 노드로 가능 다익스트라를 호출한다면

이는 모든 시작점에서 X로가는 거리를 구할 수 있는 셈이다.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
#define INF 2100000000
 
using namespace std;
 
class Node {
public:
    int index, time;
 
    Node(int index_, int time_) : index(index_), time(time_) {}
    Node(): Node(-1,-1){}
};
 
int N, M, X;
 
vector<vector<int>> nodes;        //nodes[a] : a에서 이동가능한 노드 번호의 목록
vector<vector<int>> weights;    //weights[a] : nodes[a] 와 대응되는 edge의 가중치
 
vector<vector<int>> rev_nodes;    //rev_nodes[a] : a로 올 수 있는 노드의 번호
vector<vector<int>> rev_weights;    //rev_weights[a] : rev_nodes[a]와 대응되는 edge의 가중치
 
vector<int> dist;
vector<int> rev_dist;
 
//from에서 to까지 가는 최단경로의 길이
 
 
void Dijkstra(int start, vector<vector<int>> &nodes, vector<vector<int>> &weights, vector<int> &dist) {
    int ret = INF;
 
    queue<Node> qu;
    qu.push(Node(start, 0));
 
    while (!qu.empty()) {
        Node cNode = qu.front();
        qu.pop();
 
        int from = cNode.index;
        int time = cNode.time;
 
        if (time > dist[from])
            continue;
 
        int cnt = nodes[from].size(); //현재 노드에서 이동가능한 노드의 갯수
        for (int i = 0; i < cnt; i++) {
            int to = nodes[from][i];
            int weight = weights[from][i];
 
            if (time + weight > dist[to])
                continue;
 
            dist[to] = time + weight;
            qu.push(Node(to, time + weight));
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> X;
    X--;
    nodes.assign(N, vector<int>());
    weights.assign(N, vector<int>());
    rev_nodes.assign(N, vector<int>());
    rev_weights.assign(N, vector<int>());
 
    dist.assign(N, INF);
    rev_dist.assign(N, INF);
 
    int from, to, weight;
    for (int i = 0; i < M; i++) {
        cin >> from >> to >> weight;
        from--, to--;
 
        nodes[from].push_back(to);
        weights[from].push_back(weight);
 
        rev_nodes[to].push_back(from);
        rev_weights[to].push_back(weight);
    }
 
    Dijkstra(X, nodes, weights, dist);
    Dijkstra(X, rev_nodes, rev_weights, rev_dist);
    //Rev_Dijkstra(X);
 
 
    dist[X] = 0;
    rev_dist[X] = 0;
 
    int val = -1;
    for (int i = 0; i < N; i++)
        val = max(val, dist[i] + rev_dist[i]);
    cout << val << endl;
 
    return 0;
}

 

 

기존의 간선에 대해 역방향 정보를 담은 경우 rev_ 접두사를 붙였으며 기존의 그래프와 역방향 그래프에 대해 dijkstra를 2번 호출했다.

 

일반 다익스트라 알고리즘 : 하나의 정점에서 다른 모든 정점 까지의 최단경로

간선을 뒤집은후 다익스트라 : 다른 모든 정점에서 하나의 정점까지의 최단경로

 

유용히 쓰일듯한 개념이니 잘 숙지해두자.

 

참고

우선순위 큐를 사용하지 않으면 O(V^2), 사용할 시에는 O(ElgV)의 시간 복잡도를 갖게 된다.

일반적으로 ElgV의 시간복잡도가 더 앞서는 경우가 많아서 우선순위 큐를 이용한 다익스트라를 사용하는 경우가 많지만,

완전 그래프, 즉 E = V^2인 그래프가 주어지는 문제에서는 보통 전자가 더 빠르기 때문에 우선순위 큐를 사용하지 않기도 한다.

개선된 풀이에서는 priority_queue 대신에 queue를 사용했는데 확인결과 2가지 경우 모두 4ms가 나왔다.

참고로 맨처음 다익스트라 알고리즘을 다수 호출하는 방식의 풀이에서 queue를 적용한 결과 성능은 172ms에서 124ms까지 개선된것이 확인되었다.

문제의 조건에 맞추어 priority_queue와 queue 중 무엇을 쓸지 잘 판단해야 할듯하다.