백준 최소 스패닝 트리 11971 [6개월 안에 백준 플래티넘 달성하기] 16. 최소 스패닝 트리 1197 최소 스패닝 트리 문제 풀이 최소 스패닝(신장) 트리 문제입니다. 모든 노드를 지나면서 사이클이 존재하지 않는 트리 중 간선의 합이 가장 낮은 트리를 찾으면 됩니다. 백준 class 4 문제를 모두 해결하신 분이라면 다익스트라 알고리즘을 살짝 응용하면 충분히 푸실 수 있을 겁니다. 저 또한 이처럼 해당 문제를 풀었고 이후 해당 풀이가 최소 신장트리를 구하는 프림 알고리즘이라는 것을 알게 되었습니다. 이 밖에도 크루스칼 알고리즘도 존재하는데 이 둘을 간략하게 설명드리겠습니다. 프림 알고리즘 최소 신장트리를 구하는 알고리즘입니다. 음의 간선이 존재하고 사이클이 존재할 때도 사용할 수 있습니다. 프림 알고리즘은 단순하게 노드를 하나씩 돌면서 최소 간선을 추가해 주는 방식입니다. 따라서 주로 문제에 주어진 간선.. 2024. 1. 1. 이전 1 다음 반응형
