이 문제는 문제 제목에서부터 MST 문제라는 것을 알려주고 있다. 당연히 나는 MST 알고리즘 중 내가 알고 있는 Prim알고리즘을 통해 풀었고, 아쉽게도 시간 통과를 하지 못하였다. 잘 모르는 크루스칼 알고리즘을 공부해봐야 하나 생각하며 백준 질문게시판을 둘러보았는데, 프림과 힙을 사용해서 풀었다는 사람들이 많아서 조금 충격을 받았다. 나의 다른 MST 풀이를 보면 알겠지만 나는 프림 알고리즘은 세 가지 구조를 가지고 문제를 해결한다. 1. 현재 내가 갈 수 있는 곳 중 최소 비용으로 갈 수 있는 곳을 찾는다 2. 최소로 갈 수 있는 곳을 등록한다. 3. 새로 등록한 곳에서 또 더 갈 수 있는 곳을 찾는다. 이렇게 할 때, 힙을 어디서 사용하지라는 아이디어가 쉽게 떠오르지 않았다. 하지만, 결국 프림 ..
