문제 설명
•
개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구하는 문제
예제 입력/출력
n | costs | return |
4 | [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] | 4 |
제약 조건
•
•
•
연결할 수 없는 섬은 주어지지 않는다.
문제 풀이
•
접근1 그리디 -
◦
이 문제는 최소한의 비용으로 모든 섬을 연결해야 하므로, 그리디 알고리즘을 적용할 수 있다.
◦
접근 방법
▪
모든 섬이 연결될 때까지, 가장 적은 비용의 다리부터 선택한다.
▪
섬이 연결될 때 사이클이 생기는지 확인한다.
▪
위 조건을 만족하는 대표적인 알고리즘이 Kruskal 알고리즘
◦
구현 방법
1.
비용(cost) 기준으로 간선 정렬
2.
가장 비용이 낮은 간선부터 선택
3.
선택된 간선의 두 정점이 같은 집합에 속해 있는지 확인
•
Union-Find 알고리즘을 사용하여 사이클이 발생하는지 검사
◦
만약 두 정점이 이미 같은 집합이라면, 해당 간선을 선택하지 않는다.
◦
두 정점이 다른 집합이라면, 해당 간선을 선택하고 두 집합을 합친다.
union-find 알고리즘 이용
4.
모든 섬이 연결될 때까지 2~3번 과정 반복
◦
시간 복잡도
▪
Union-Find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선들을 정렬하는 시간에 좌우된다.
•
따라서, 시간 복잡도는 간선을 정렬하는 시간인
풀이 코드
def solution(n, costs):
# find 함수 (경로 압축 적용)
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
# union 함수 (두 집합을 합치기)
def union(x, y):
root_x = find(x)
root_y = find(y)
if root_x != root_y:
root[root_y] = root_x
# 1. 비용 기준으로 간선 정렬
costs.sort(key=lambda x: x[2])
# 2. 유니온-파인드 알고리즘을 위한 root 배열 초기화
root = list(range(n))
total_cost = 0 # 최소 비용 저장 변수
edge_count = 0 # 선택된 간선 개수
# 3. 가장 비용이 낮은 간선부터 선택
for a, b, cost in costs:
if find(a) != find(b): # 사이클이 발생하지 않는다면
union(a, b) # 두 노드를 같은 집합으로 합침
total_cost += cost
edge_count += 1
if edge_count == n - 1: # 모든 섬이 연결되었으면 조기 종료
break
return total_cost
Python
복사
