크루스칼 알고리즘1 [백준 1197] 최소 스패닝 트리 (Swift) https://www.acmicpc.net/problem/1197크루스칼 알고리즘가중치 그래프의 간선 정보 ("노드1, 노드2, 가중치")가 배열로 주어지고, 모든 정점을 잇는 간선의 가중치 합이 최소가 되는최소 스패닝 트리의 가중치 합을 구하는 문제 접근방법처음에 다익스트라로 풀었다가 프림으로 풀었다가 안돼서 결국 크루스칼로 풀었다. 크루스칼 알고리즘의 핵심은1. 간선을 가중치 순으로 오름차순 정렬한다.2. 최소 간선 부터 살펴보면서 (담으면서) 선택된 간선에 의해 이어진 노드들의 부모노드를 통일시킨다.3. 이때, 간선을 선택할 때는 현재 이미 이어져있는 간선들에 연결된 노드들과 사이클을 형성하지 않도록 하는 조건을 건다.인데 이를 위해서는 1. [가중치, 노드1, 노드2]를 원소로 갖는 배열을 가중.. 2025. 2. 6. 이전 1 다음 728x90
