전력난 [백준:6497] 골드

해당문제는 그래프  최소 스패닝 트리로 풀 수 있는 문제다. 최소 스패닝트리는 프림과 크루스칼 알고리즘 으로 플수있다. 해당문제는  프림으로 풀었다 프림이 기본적인 알고리즘은 더 쉽다.   간단하게 말하자면  다익스트라가 누적과 다음노드로 가는 가격을 본다면 프림의 경우는 현재 갈 수 있는 간선들 중 가장 값싼 간선을 우선적으로 본다는 것이다,. 다시 문제로 돌아와 "켜져 있는"위치로만 가야 하기에 다익스트라는 다시 왔을 때 가격을 비교해야 하기에 어울리지 않을 수 있다.  코드르 보면서 설명해 보자 #include#include #include#include#include using namespace std;unordered_map>> Spninmap;unordered_map maps;//unorder..
알고리즘 2024. 11. 14. 23:24
1