Prim1

• [백준/BOJ] 14950번: 정복자 문제 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 해설 모든 도시를 정복하는데 드는 최소 비용을 구하는 문제이다. 이 문장을 보고 MST 알고리즘을 떠올려야 한다. MST를 떠올렸다면, 이를 크루스칼 알고리즘과 프림 알고리즘 중 어떤 알고리즘으로 해결할지 정해야 한다. 이 문제는 1번 도시부터 시작해서 이와 연결된 도시를 정복해나가야 한다. 따라서 프림 알고리즘이 더 적절하다 생각했다. 문제를 보면 "한 번 도시가 정복되면, 모든 도시는 경계를.. PS(Problem Solving)/BOJ 2022. 7. 28.