반응형
해당문제는 그래프 최소 스패닝 트리로 풀 수 있는 문제다.
최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다.
해당문제는 프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.
간단하게 말하자면 다익스트라가 누적과 다음노드로 가는 가격을 본다면
프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,.
다시 문제로 돌아와
"켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.
코드르 보면서 설명해 보자
#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;
}
'알고리즘' 카테고리의 다른 글
| 알고리즘 [flood fill] (0) | 2024.11.12 |
|---|---|
| 영우의 기숙사 청소 [백준 : 15806번] (0) | 2024.11.05 |
| 부분합 알고리즘 (0) | 2024.10.29 |
| 타잔(Tarjan) 알고리즘 (0) | 2024.07.20 |
| 위상정렬 알고리즘 (1) | 2024.03.29 |
