문제 풀이/백준 (BOJ)
[백준/BOJ] 1197번: 최소 스패닝 트리( Minimal Spanning Tree ) - C++ 문제 풀이
문제 설명 문제 링크: https://www.acmicpc.net/problem/1197 풀이이 문제는 그래프가 주어졌을 때, 그 그래프로부터 최소 신장 트리의 가중치 합을 출력하는 문제입니다. 여기서, 최소 신장 트리( Minimal Spanning Tree )는 주어진 그래프에서, 모든 정점을 지나는 트리 중에 가장 작은 가중치 합을 가진 트리를 말합니다. 이 최소 신장 트리를 구하는 알고리즘으로 Kruskal과 Prim 알고리즘이 있는데, 이 글에선 Kruskal 알고리즘을 사용했습니다.이 알고리즘은 가중치가 작은 간선을 우선적으로 선택하여, 신장 트리를 구성하는 알고리즘입니다.그 과정에서, 가중치를 기준으로 간선을 정렬해야 하고, 추가되는 간선이 순환 경로를 만드는지를 검사하는 기능이 필요합니다...
2024. 7. 4.
