kursckal1

• 

  [백준/BOJ] 16202번: MST 게임 문제 https://www.acmicpc.net/problem/16202 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 해설 제목에서부터 알 수 있듯이 MST를 응용하는 문제이다. 최소 신장 트리를 구하기 위해 크루스칼 알고리즘을 사용하였다. 문제에서 가장 중요한 문장은 아래 문장이다. 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다. 결론적으로는 한 턴이 끝날 때마다 가장 작은 간선을 제거하여 k만큼 .. PS(Problem Solving)/BOJ 2022. 8. 12.