[C++] 백준 1238 - 파티

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

1238번: 파티

 

<알고리즘 분류>

   - 그래프 이론(Graph Theory)

   - 다익스트라(Dijkstra)

 

<풀이> 

  1. 각 마을에서 파티장소까지 가고, 파티장소에서 다시 자신의 마을로 돌아오는 최단경로를 모든 vertex에 따라 구해야 한다. 그림은 다음과 같다. (4번 마을에 사는 사람에 대한 예시도 적었다.)

2. 결국 중요한 점은, 기존의 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만,

이 문제는 (A->X로 가는 최단거리) +  (X->A로 돌아오는 최단거리)를 구해야 한다.

 다익스트라는 처음 위치만 안다면, 나머지 노드까지 가는 최단거리를 모두 구할 수 있다. 그래서 (X->A로 돌아오는 최단거리)는 다익스트라를 1번만 사용함으로써 쉽게 구할 수 있다. 

문제는 (A->X로 가는 최단거리)이다. 시작노드를 모두 다르게 잡기 때문에, 다익스트라를 노드 개수만큼 실행해 주어야 한다. 

문제에서 노드(마을)의 개수는 N(1 ≤ N ≤ 1,000)이고, 간선(경로의 개수)는  M(1 ≤ M ≤ 10,000) 이므로, 

다익스트라 알고리즘(우선순위 큐 적용)의 시간복잡도가 O(MlogN)인 것을 감안하면,

위에서 설명한 코드의 전체적인 시간복잡도는 O(N * MlogN) 이므로, 1000*10000*log(1000) = 약 2천만 --> 제한시간 1초(1억) 내에 해결이 가능할 것으로 보인다. 결국 아래 코드는 통과!

 

<코드 (시간복잡도 O(N * MlogN), 최적화 X)>

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 1000000000

int minCost[20001]; //최소비용
vector<pair<int, int>> a[20001]; // 간선
// a[i] ={j, k} 일 때, i->k로 가는 가중치가 j. 

int N, M, X; // 마을 수, 간선 수, 파티장소
int MinMap[1001][1001]; // start-> end로 갈 떄의 최단거리. 

void dijkstra(int start, int end){

    minCost[start] = 0;
    priority_queue<pair<int,int>> pq;
    //pq[i] = {j, k} 시, i-> k의 가중치는 j.
    pq.push({0, start});

    while(!pq.empty()){
        int current = pq.top().second; //현재 노드의 인덱스
        int distance = -pq.top().first; 
        pq.pop();
        
        if(minCost[current] < distance) continue;
        for (int i=0; i<a[current].size(); i++){ //current와 연결돼있는 간선
            //선택노드의 인접노드들
            int next = a[current][i].second;
            int nextDistance = distance + a[current][i].first;
            //기존의 최소 비용보다 더 저렴하면 교체. 
            if (nextDistance < minCost[next]){
                
                minCost[next] = nextDistance;
                pq.push({-nextDistance, next});
                
            }
        }
        
    }

    MinMap[start][end] = minCost[end];

}

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> X;

    for (int i=1; i<=N; i++){
        minCost[i] = INF; //초기화 
    }

    for (int i=0; i< M; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({w,v});
    }

    for (int start=1; start<=N; start++){
        dijkstra(start, X);
        for (int i=1; i<=N; i++){
        minCost[i] = INF; //초기화 
        } 
    }
    dijkstra(X, 1);
    for (int i=1; i<=N; i++){
        MinMap[X][i] = minCost[i];
    }

    int maxtime = 0;
    for (int i=1; i<=N; i++){
        if(MinMap[i][X] + MinMap[X][i] > maxtime) 
        maxtime = MinMap[i][X] + MinMap[X][i];
    }

    cout << maxtime;

}

 

3. 하지만, 만약 간선의 최대개수가 100,000개이고 노드의 최대개수가 10,000개라면 위의 코드는 시간초과가 발생한다. 그래서 조금 더 응용해봐서, 다익스트라를 2번만 사용하는 코드를 구현해 보았다. 

(X->A로 돌아오는 최단거리)는 다익스트라를 1번만 사용함으로써 쉽게 구할 수 있고,

(A->X로 가는 최단거리)는 간선의 방향을 모두 역방향으로 돌려서 구현했다.

(그러면 자연스럽게 X가 출발점이 될 수 있으므로, 구할 수 있다.) 

코드는 다음과 같다.

 

<코드 (시간복잡도 O(MlogN), 최적화 0)>

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 1000000000

int minCost[2][20001]; //최소비용
vector<pair<int, int>> a[2][20001]; // 간선

// a[i] ={j, k} 일 때, i->k로 가는 가중치가 j. 

int N, M, X; // 마을 수, 간선 수, 파티장소

void dijkstra(int k){
    minCost[k][X] = 0; //X는 출발장소 
    priority_queue<pair<int,int>> pq;
    //pq[i] = {j, k} 시, i-> k의 가중치는 j.
    pq.push({0, X});

    while(!pq.empty()){
        int current = pq.top().second; //현재 노드의 인덱스
        int distance = -pq.top().first; 
        pq.pop();
        
        if(minCost[k][current] < distance) continue;
        for (int i=0; i<a[k][current].size(); i++){ //current와 연결돼있는 간선
            //선택노드의 인접노드들
            int next = a[k][current][i].second;
            int nextDistance = distance + a[k][current][i].first;
            //기존의 최소 비용보다 더 저렴하면 교체. 
            if (nextDistance < minCost[k][next]){
                
                minCost[k][next] = nextDistance;
                pq.push({-nextDistance, next});
                
            }
        }
        
    }



}


int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> X;

    for (int i=1; i<=N; i++){
        minCost[0][i] = INF; //초기화 
        minCost[1][i] = INF; //초기화 
    }

    for (int i=0; i< M; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[0][u].push_back({w,v}); //정방향 : 파티 장소에서 각 노드까지 가는 모든 최단거리 구하기. 
        a[1][v].push_back({w,u}); //역방향 : 노드에서 파티 장소까지 가는 모든 최단거리 구하기. 
    }

    dijkstra(0); //정방향 : 파티 장소에서 각 노드까지 가는 모든 최단거리 구하기.
       
    dijkstra(1); //역방향 : 노드에서 파티 장소까지 가는 모든 최단거리 구하기.

    int maxtime = 0;
    for (int i=1; i<=N; i++){
        if(minCost[0][i] + minCost[1][i] > maxtime) 
        maxtime = minCost[0][i] + minCost[1][i];
    }

    cout << maxtime;
}