백준 2211번 네트워크 복구 - C++ 풀이

---

 

1. 다익스트라 알고리즘을 사용해서 1번 정점에서 각 정점으로의 최단 거리를 구한다.
2. 1번 과정에서 각 정점을 최단거리로 방문하기 위해 직전에 방문한 정점을 기록해둔다.
3. 2번 과정에서의 기록을 가지고 최단거리로 전송하기 위해 필요한 간선들만 골라낸다.

 

1. 다익스트라 알고리즘을 사용해서 1번 정점에서 각 정점으로의 최단 거리를 구한다.

 1번 슈퍼컴퓨터에서 각 컴퓨터로 최소 시간으로 패킷을 전송해야 한다. 따라서 1번 컴퓨터에서 각 컴퓨터까지의 최단 거리를 구해야 한다. 한 정점에서 다른 모든 정점으로의 최단거리는 다익스트라 알고리즘을 사용해서 구할 수 있다.

 

2. 1번 과정에서 각 정점을 최단거리로 방문하기 위해 직전에 방문한 정점을 기록해둔다.

 구해야 하는 것은 최단 시간(거리)이 아니라 최단 시간으로 전송하기 위해 필요한 간선의 목록이다. 따라서 다익스트라 알고리즘을 수행하는 과정에서 정점의 최단거리를 갱신할 때 해당 최단거리를 갖도록 하기 위해 거쳐온 정점을 기록해두자. 아래 코드에서는 before 배열에 기록하였다.

 

3. 2번 과정에서의 기록을 가지고 최단거리로 전송하기 위해 필요한 간선들만 골라낸다.

 유니온-파인드에서의 find 연산과 같은 방식으로 before를 역추적하면, i번 간선을 최단거리로 방문하기 위해 거쳐온 정점 및 간선을 전부 구할 수 있다. 중복이 없도록 set 자료구조를 사용하여 최단거리로 전송하기 위해 필요한 간선들의 집합을 구해준다.

반응형

---

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

using namespace std;

typedef pair<int, int> pii;
const int MAX = 1001, INF = 987654321;

int N, M, A, B, C;
vector<pii> adj[MAX];

set<pii> dijkstra() {
    set<pii> ret;
    vector<int> d(N+1, INF);
    vector<int> before(N+1);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    for (int i=0; i<=N; i++) before[i] = i;
    d[1] = 0;
    pq.push({0, 1});
    
    while (!pq.empty()) {
        int currD = pq.top().first;
        int curr = pq.top().second;
        pq.pop();
        
        if (currD > d[curr]) continue;
        
        for (auto x: adj[curr]) {
            int next = x.first;
            int w = x.second;
            
            if (d[curr]+w < d[next]) {
                d[next] = d[curr]+w;
                before[next] = curr;
                pq.push({d[next], next});
            }
        }
    }

    for (int i=1; i<=N; i++) {
        int p = i;
        
        while (p != before[p]) {
            ret.insert({min(p, before[p]), max(p, before[p])});  
            p = before[p];
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        cin >> A >> B >> C;
        adj[A].push_back({B, C});
        adj[B].push_back({A, C});
    }
    
    set<pii> ans = dijkstra();
    
    cout << ans.size() << "\n";
    for (auto edge: ans) {
        cout << edge.first << " " << edge.second << "\n";
    }

    return 0;
}