[BOJ] 2211번 : 네트워크 복구

문제 링크 : 백준 2211번

[문제 접근]

기본적인 다익스트라를 이용해서 풀었는데 이 문제에서는 최단 거리의 경로를 출력해줘야한다.

Union-find 개념과 비슷하게 parent배열을 이용해 경로를 계속 갱신에 주었다.
현재(cur)에서 다음 노드(next)로 간다고 할 때 그 경로가 최단 경로이면 parent[next] = cur 즉, next에 오기전 노드는 cur이다.

⭐️ 모든 최단 거리를 구했으면 경로를 거슬러 올라가면서 set에 경로를 넣어주었다.(중복을 제거해주기 위해)
마지막으로 set의 크기와 set을 순회하면서 정답을 출력해주면 된다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <vector>
#include <set>

using namespace std;
#define MAX 1000000

int n, m;
int dist[1001]; // 최단 거리
int parent[1001]; // 경로를 담을 배열
typedef pair<int, int> p;
vector<p> arr[1001];
set<string> s;

void Dijkstra(int start) {
    memset(dist, MAX, sizeof(dist));
    priority_queue<p, vector<p>, greater<p> > pq;
    pq.push(p(0, start));
    dist[start] = 0;
    
    parent[start] = 0;

    while(!pq.empty()) {
        int cur = pq.top().second;
        pq.pop();

        for(int i=0 ; i<arr[cur].size() ; i++) {
            int next = arr[cur][i].first;
            if(dist[next] > dist[cur] + arr[cur][i].second) {
                dist[next] = dist[cur] + arr[cur][i].second;
                pq.push(p(dist[next], next));
                parent[next] = cur; // 도착 경로를 계속 갱신(next에 오는 최단경로는 cur이므로)
            }
        }
    }

    // 경로를 거슬러 올라가면서 set에 경로를 넣어준다(중복 제거)
    for(int i=2 ; i<=n ; i++) {
        int now = i;
        while(parent[now] != 0) {
            string temp = to_string(now) + " " + to_string(parent[now]);
            s.insert(temp); // 출력은 임의의 순서
            now = parent[now];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    for(int i=0 ; i<m ; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        arr[a].push_back(p(b, c));
        arr[b].push_back(p(a, c));
    }

    Dijkstra(1);
    
    set<string>::iterator it;
    cout << s.size() << "\n";
    for(it=s.begin() ; it!=s.end() ; it++) {
        cout << *it << "\n";
    }
    
    return 0;
}