전력난 [백준:6497] 골드

 

해당문제는 그래프  최소 스패닝 트리로 풀 수 있는 문제다.

 

최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다.

 

해당문제는  프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.

 

 

 

간단하게 말하자면  다익스트라가 누적과 다음노드로 가는 가격을 본다면

 

프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,.

 

다시 문제로 돌아와

 

"켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.

 

 

코드르 보면서 설명해 보자

 

#include<iostream>
#include <queue>
#include<tuple>
#include<vector>
#include <unordered_map>
using namespace std;
unordered_map<int, vector<pair<int, int>>> Spninmap;
unordered_map<int, bool> maps;
//unordered_map<int, int> sp_map;
int gagungchi = 0;
int k = 0;
priorityqueue<pair<int, int>> q;
void minSpningTree() {
    int a = 0, b = 0;
    int n = 0, m = 0, v = 0;
    while (true)
    {
        Spninmap = *new unordered_map<int, vector<pair<int, int>>>();
        maps = *new unordered_map<int, bool>();
        gagungchi = 0;
        k = 0;
        cin >> a >> b;
        if (a == 0 && b == 0) return;
        //그래프로 섬들을 만들어준다.
        for (int i = 0; i < b; i++) {
            cin >> n >> m >> v;
            Spninmap[n].push_back(make_pair(-v, m));
            Spninmap[m].push_back(makepair(-v, n));
            k += v;
        }
        //시작위치 n 으로 잡고 갈수있는 간선들을 받아준다.
        for (auto i : Spninmap[n]) {
            q.push(i);
        }
        //현재위치 탐색완료
        maps[n] = true;
        while (!q.empty())
        {
            auto c = q.top();
            q.pop();
            if (maps[c.second] == true) continue;
            maps[c.second] = true;
            //전력 업데이트
            gagungchi += -(c.first);
            //현재 갈수있는 간선들 추가
            for (auto i : Spninmap[c.second]) {
            //갔던섬이면 빼주기
                if (maps[i.second] == true) continue;
                q.push(i);
            }
        }
        cout << k - gagungchi<<"\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(NULL);
    minSpningTree();
    return 0;
}