📒 문제 설명
🔖 https://school.programmers.co.kr/learn/courses/30/lessons/42861
📖 문제
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
🚫 제한사항
- 섬의 개수 n은 1 이상 100 이하입니다.
- costs의 길이는 ((n-1) * n) / 2이하입니다.
- 임의의 i에 대해,
costs[i][0]와costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고,costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.- 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
✏️ 풀이 과정
📝 접근 및 이론적 배경
- 기본적인 최소 비용 신장 트리를 구하는 문제이다.
🔎 신장 트리 (Spanning Tree)
- 모든 정점이 포함되어 있으면서 정점 간 서로 연결되어 있고, 사이클이 존재하지 않는 트리이다.
- 신장 트리의 정점의 개수가
n일 때, 간선의 개수는n - 1이다.
🔎 크루스칼 알고리즘 (Kruskal's Algorithm)
- 가중치 그래프에서 최소 비용 신장 트리를 찾는 그리디 알고리즘이다. 가장 낮은 가중치를 가진 간선부터 추가하여 트리를 구성한다.
- 서로 다른 두 집합을 병합하는
union연산과, 특정 원소가 속해있는 집합을 반환하는find연산을 이용하여 사이클을 처리한다.
✨ 소스 코드
import sys
input = sys.stdin.readline
def solution(n, costs):
answer = 0
parent = [i for i in range(n)]
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
# 가중치 순으로 정렬
costs.sort(key=lambda x: x[2])
for c in costs:
root1 = find(c[0])
root2 = find(c[1])
if root1 != root2:
parent[root2] = root1 # union
answer += c[2]
return answer