[BOJ] 백준 1197 최소 스패닝 트리 (Swift)

문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

풀이

문제 그대로 최소 스패닝 트리(MST)를 구하는 문제입니다.
최소 스패닝 트리를 구하는 방법으로는 크루스칼 알고리즘, 프림 알고리즘을 활용해서 구할 수 있습니다.

저는 크루스칼 알고리즘을 활용하여 풀이하였습니다.
간선을 비용의 오름차순 순으로 정렬하여, 비용이 적은것 부터 확인하면서 사이클이 이루어지지 않는다면 연결시켜 줍시다.

연결시킨 비용의 총 합이 가중치가 됩니다.

소스코드

후기

MST를 구하는 알고리즘에 대해 안다면 쉽게 풀 수 있는 문제였습니다.