섬 연결하기 문제 바로가기
코딩 테스트 연습 > 탐욕법(Greedy) > 섬 연결하기
level 3
해결 방법
주요 변수 설명
p 리스트를 통해 섬(노드)이 어느 섬과 연결되었는지 또는 연결이 안되었는지 확인가능하다.
p의 초기 설정(n = 4일 때 가정)
p = [0, 1, 2, 3]
각 인덱스마다 자기 자신의 섬과 연결된 것으로 기본 설정을 한다.
ex) 초기 설정에서 만약 0번 섬과 1번 섬이 연결되었을 경우 p는 다음과 같다.
p = [0, 0, 2, 3]
1번 섬의 부모노드를 0번 섬으로 저장하여 연결됨을 보인다.
구현 과정
Kruskal MST 알고리즘 이용 ★
costs에서 가중치가 작은 순으로 정렬한다.
while 문을 통해서 가중치가 작은 순서대로 costs를 pop하여 확인한다.
u, v, wt = costs.pop(0)연결된 u, v의 섬이 서로 사이클이 없다면 (즉 연결가능하다면!)
if find(u) != find(v):- 두 섬을 연결한다.
union(u, v) - 출력할 최소비용을 저장한
cost변수에 가중치를 더한다. - 간선을 연결했기에
tree_edges에 1을 더한다.
- 두 섬을 연결한다.
연결된 u, v의 섬이 사이클이 있다면 패스!
이유
최소 비용으로 모든 섬을 연결하는 mst의 조건을 만족하기 위해서는 사이클이 없는 섬끼리 연결해야한다!
→ mst의 조건인 간선의 개수가 n - 1인 경우 break를 통해 종료시킨다.
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def solution(n, costs):
costs.sort(key = lambda x: x[2]) # 가중치가 작은 순으로 정렬하기
p = [i for i in range(n)]
tree_edges = 0
cost = 0
def find(u): # 연결된 상위 부모노드를 찾아주는 함수
if u != p[u]:
p[u] = find(p[u])
return p[u]
def union(u, v): # u, v의 섬을 연결해주어 간선이 연결되는 함수
# 각 섬의 부모 노드를 찾기
root1 = find(u)
root2 = find(v)
p[root2] = root1 # 부모노드를 갱신하여 간선 연결하기
while True:
if tree_edges == n - 1: # mst 조건 : 모든 섬이 통하는 경우
break
u, v, wt = costs.pop(0)
if find(u) != find(v): # 사이클이 아니라면! 연결 가능한 조건
union(u, v) # 간선 연결하기
cost += wt # 비용에 가중치 추가하기
tree_edges += 1 # 간선 추가됨을 확인할 수 있도록 변수에 저장하기
return cost