[백준][C++] 1238 파티

 

 

 

알고리즘 종류

    - 최단거리

    - Dijkstra

 

 

 

사고 과정

    - 방법 1

        1. Dijkstra를 n번하여 구하는 방법

        2. i 번째 정점에서 모든 정점으로 가는 최단 거리 구하기

        3.  n 번째까지 구한 뒤, 최단 거리가 저장된 배열에서 최대 이동 거리 구하기

 

    - 방법 2

        1. 모든 정점 => x 정점 => 모든 정점 으로 구하는 방법

        2. x 정점 => 모든 정점으로 가는 최단 거리는 입력된 그래프 그대로 사용하여 Dijkstra 사용

        3. 모든 정점 => x 정점으로 가는 최단 거리는 입력된 그래프의 방향을 거꾸로 하여 Dijkstra 사용

 

구현(C++)

    - 방법 1

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> 
#include <queue>
 
using namespace std;
 
int n, m, x;
int answer = 0;
int INF = 987654321;
 
// 모든 정점에서 모든 정점으로 가는 최단 거리 기록하는 배열  
int dist[1010][1010];
// 입력을 받을 container  
vector<vector<pair<int, int> > > edges;
 
void dijkstra(int src){
    
    dist[src][src] = 0;
    priority_queue<pair<int, int> > pq;
     
    pq.push({src, 0});
     
    while(!pq.empty()){
         int cur_node = pq.top().first;
         int cur_dist = -pq.top().second;
         pq.pop();
         
         if(dist[src][cur_node] < cur_dist) continue;
         
         for(int i=0; i<edges[cur_node].size(); i++){
             int next_node = edges[cur_node][i].first;
             int next_dist = cur_dist + edges[cur_node][i].second;
             
             if(next_dist < dist[src][next_node]){
                 dist[src][next_node] = next_dist;
                 pq.push({next_node, -next_dist});
            }
        }
    }
}
 
int main(void){
    
    cin >> n >> m >> x;
    
    // container의 크기를 조절  
    edges.resize(n+1);
    // 비용을 기록할 배열 초기화  
    fill(&dist[0][0], &dist[n+1][n+1], INF);
    
    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
    }
    
    // Dijkstra를 n번 수행  
    for(int i=1; i<=n; i++){
        dijkstra(i);
    }
    
    // 최대 비용 구하기  
    for(int i=1; i<=n; i++){
        answer = max(answer, dist[i][x] + dist[x][i]);
    }
    
    cout << answer << endl;
}
 
 

 

 

    - 방법 2

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm> 
#include <queue>
 
using namespace std;
 
int n, m, x;
int answer = 0;
int INF = 987654321;
 
int result[1001];
vector<vector<pair<int, int> > > edges1;
vector<vector<pair<int, int> > > edges2;
 
void dijkstra(int src, vector<vector<pair<int, int> > > edges) {
 
    int dist[1001];
    fill(&dist[0], &dist[n + 1], INF);
    dist[src] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({ src, 0 });
 
    while (!pq.empty()) {
        int cur_node = pq.top().first;
        int cur_dist = -pq.top().second;
        pq.pop();
 
        if (dist[cur_node] < cur_dist) continue;
 
        for (int i = 0; i<edges[cur_node].size(); i++) {
            int next_node = edges[cur_node][i].first;
            int next_dist = cur_dist + edges[cur_node][i].second;
 
            if (next_dist < dist[next_node]) {
                dist[next_node] = next_dist;
                pq.push({ next_node, -next_dist });
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
        result[i] += dist[i];
}
 
 
int main(void) {
 
    cin >> n >> m >> x;
 
    edges1.resize(n + 1);
    edges2.resize(n + 1);
 
    for (int i = 0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges1[a].push_back({ b,c });
        edges2[b].push_back({ a, c });
    }
 
    dijkstra(x, edges1);
    dijkstra(x, edges2);
 
    for (int i = 1; i <= n; i++) {
        answer = max(answer, result[i]);
    }
 
    cout << answer << endl;
}

 

 

 

시행착오

    - 방법 1대로 구현하다가 차라리 Floyd-Warshall로 할까 생각했다. 그런데 Floyd-Warshall의 시간 복잡도는 n^3이므로 10^9가 되면 시간 초과가 나올 것 같아서 하지 않기로 했다.

    - 방법 1대로 구현하니 제출은 되었다. 그런데 시간이 꽤 오래 걸리는 것 같았다. 굳이 모든 정점들 다 구해야 할까? 라는 생각이 들었다. 그래서 방법을 찾기 시작했다.

    - 그래프의 방향을 반대로 해서 Dijkstra를 하면 모든 정점에서 특정 정점까지 가는 최단 거리를 구할 수 있다는 것을 검색을 통해서 알게 되었다. 대단했다. 

    - 아래의 표를 보면, 속도 차이를 볼 수 있다. 첫 번째가 방법 2, 두 번째가 방법 1을 사용한 결과이다.