[ BOJ 백준 2211번 - 네트워크 복구 ] 해설 및 코드

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

 

목적

본문을 요약하자면 최소 스패닝 트리를 구하라는 것이다.

 

접근법

1. 다익스트라 알고리즘을 활용하여 접근하자.

 

#include<bits/stdc++.h>
#define f(i,r,l) for(int i=r;i<=l;++i)
using namespace std;
 
struct info {
    int w, v;
    bool operator<(const info& oth)const { return w > oth.w; }
};
 
int n, m, g[1001][1001] = {};
const int INF = 1e4;
 
void solution() {
    int a[1001], b[1001];
    f(i, 1, n)a[i] = INF; a[1] = 0;
 
    priority_queue<info> q;
    q.push({ 0,1 });
 
    while (!q.empty()) {
        int w = q.top().w, v = q.top().v; q.pop();
        if (a[v] != w)continue;
 
        f(i, 1, n)if (g[v][i]) {
            int tmp = a[v] + g[v][i];
            if (a[i] > tmp) {
                a[i] = tmp;
                b[i] = v;
                q.push({ tmp,i });
            }
        }
    }
 
    cout << n - 1 << '\n';
    f(i, 2, n)cout << b[i] << ' ' << i << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }
    solution();
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.