[백준][C++] 2211: 네트워크 복구

문제

2211번: 네트워크 복구

풀이

다익스트라에 경로 추적을 결합한 문제이다. 

 

처음 문제를 읽었을 때, 최소 스패닝 트리 문제인줄 알았지만 최소 스패닝 트리로 접근할 경우 문제의 두번째 조건이 만족하지 않는다는 것을 알았다. 최소 스패닝 트리로 네트워크를 만들었을 때는 그래프의 가중치의 합이 최소인 그래프가 만들어지지, 최단 경로로 그래프를 만들어 주지는 않을 수 있다. 

그러므로, 다익스트라로 접근하였고 필요한 것은 최단 거리가 아니라 연결된 간선이 필요하므로, 경로 추적이 필요했다.

• 다익스트라 도중에 최단 경로가 갱신될 때, 현재 노드의 부모 노드를 갱신한다.
  • next_node를 최단 경로로 도달하기 위해서는 current_node애서부터 와야 한다. 
• 1번 컴퓨터에서 모든 컴퓨터로의 경로가 필요하고, 최단 경로로만 그래프가 만들어져야 하므로, 복구된 네트워크의 간선의 수는 N - 1개이다. 
• 2번 컴퓨터부터 자신과 자신의 부모를 출력한다. 이것이 연결된 간선이다. 

코드

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

using namespace std;

vector<vector<pair<int, int>>> edges;
vector<int> dist;
int parent[1001];

void dijkstra(int start)
{
    dist[start] = 0;
    parent[start] = start;

    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));

    while (!pq.empty())
    {
        int current_node = pq.top().second;
        int current_dist = (-1) * pq.top().first;
        pq.pop();

        if (dist[current_node] < current_dist)
        {
            continue;
        }

        for (auto edge : edges[current_node])
        {
            int next_node = edge.second;
            int next_dist = edge.first + current_dist;

            if (next_dist < dist[next_node])
            {
                dist[next_node] = next_dist;
                pq.push(make_pair((-1) * next_dist, next_node));

                // next_node를 최단 경로로 도달하기 위해서는 반드시 current_node에서부터 도달한다. 
                parent[next_node] = current_node;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    edges.resize(N + 1);
    dist.resize(N + 1, INT_MAX);

    for (int i = 0; i < M; ++i)
    {
        int A, B, C;
        cin >> A >> B >> C;

        edges[A].push_back(make_pair(C, B));
        edges[B].push_back(make_pair(C, A));
    }

    dijkstra(1);

    // 노드를 모두 연결해야 하므로 간선의 수는 N - 1개이다. 
    cout << N - 1 << '\n';
    // 2번 노드부터 자신과 부모 노드를 출력한다. 
    for (int i = 2; i <= N; ++i)
    {
        cout << i << " " << parent[i] << '\n';
    }

    return 0;
}