BOJ 2211 네트워크 복구

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

2211번: 네트워크 복구

일전에 작성했던 간단한 크루스칼 알고리즘으로 접근했다가 오답이 나왔다. 

문제 이해를 조금 잘못했는데, 임의의 정점간 통신에 걸리는 시간이 원래 네트워크 통신 시간보다 길지 않도록 연결해야 하므로 간선의 가중치의 합이 최소이게 하는 트리를 찾는 MST 알고리즘은 따라서 적절하지 않다.

 

모든 노드들의 합이 최소라고 해서, 그 노드들이 슈퍼컴퓨터로 부터 최단거리임을 보장할 수 없기 때문이다.

 

두 번째 조건이 다익스트라 알고리즘을 이용하라고 말해주고 있다.

2. ... 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

다익스트라를 이용하는 문제인것같은 느낌이 들었지만 사실 최단경로 자체를 출력해야 하는 문제이므로, 경로를 어떻게 저장할까 하는 문제도 있었다. 기본 다익스트라 알고리즘은 시작 정점에서 모든 정점까지의 최단 거리를 배열에 저장하는 방식으로 돼 있으므로, 시작 정점에서 현재 방문중인 정점(정점을 방문했을 때에는 시작 정점부터 그 정점까지의 거리가 최단 거리이므로 방문)과 그 부모 정점을 저장하면 최단 경로를 저장할 수 있다.

 

 

지금은 왜 잘 동작하는지를 알지만. 코딩하는 과정에서는 경로 추가 과정에서 최단 거리가 업데이트 되며 최단거리 후보들의 중복이 이루어지지 않을까 걱정이 됐는데, 최단 거리가 아니면 경로 추가가 안되도록 하는게 중요하다.

따라서 아래서 볼 continue의 역할이 굉장히 중요하다. 

 

#include <iostream>
#include <vector>
#include <queue>
#define Adj_List vector<Edge>

struct Edge {int p,cur,w;
    bool operator<(const Edge& a) const { return w > a.w; }
    Edge() = default;
    Edge(int v, int w, int p=0) : cur(v), w(w), p(p) {}
};
int N,E;
using namespace std;
vector<Edge> res;
void dijkstra(Adj_List G[], int d[] ,int s) {
    priority_queue<Edge> PQ;
    fill(d,d+N+1,INT32_MAX); // 시작 정점에서 모든 정점까지의 거리 초기화
    d[s] = 0; // 시작 정점 0으로 초기화

    PQ.push({s,0});
    while(!PQ.empty()) {
        Edge e = PQ.top();
        PQ.pop();
        if(d[e.cur] < e.w) continue;
        // 시작 정점에서 cur 정점까지 현재 edge(e)를 이용한 거리가 최단 거리가 아니면 continue
        // 최단 거리가 아니면 res에 경로 추가가 안되기 때문에 최단경로가 여러개 추가되지 않는다.
        
        // 부모 존재하면 res에 push // 시작 정점 때문에
        if(e.p != 0) res.push_back(e);
        for(Edge adj : G[e.cur]) { // 현배 방문중인 정점에 인접한 모든 정점에 대해
            int nDist = adj.w + d[e.cur], nNode = adj.cur;
            if(d[nNode] > nDist) {
                d[nNode] = nDist;
                PQ.push({nNode,nDist,e.cur}); 
                // 각각 다음 방문할 정점, 업데이트한 거리, 다음 방문할 정점의 부모 정점
            } // 거리 업데이트
        }
    }
}
int main() {
    scanf("%d%d",&N,&E);
    int d[N+1];
    int s;
    Adj_List G[N+1];

    for(int i=0;i<E;++i) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dijkstra(G,d,1);
    printf("%d\n",res.size());
    for(auto e:res)
        printf("%d %d\n",e.p,e.cur);
}

 

이 문제 덕택에 왜 다익스트라를 수행한 결과는 시작 정점을 루트로 하는 트리인지 잘 이해하게 되었다. (시작 정점에서 모든 정점까지의 최단 경로는 하나이기 때문에)