문제 설명
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의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
<코드>
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if rootX != rootY:
parent[rootY] = rootX
def solution(n, costs):
# 간선을 비용을 기준으로 정렬
costs.sort(key=lambda x: x[2])
parent = [i for i in range(n)]
total_cost = 0
for u, v, cost in costs:
# 두 노드의 루트가 다르면 (즉, 연결되지 않았으면)
if find(parent, u) != find(parent, v):
union(parent, u, v)
total_cost += cost
return total_cost
<풀이과정>
- find 함수: 특정 노드 x가 속한 집합의 "루트"를 찾아 두 노드가 같은 집합에 속하는지를 확인
- 트리 구조에서 노드 x가 속한 집합의 루트 노드 찾기
- parent[x] != x인 경우, 즉 x가 자신의 루트가 아니라면, x의 부모를 재귀적으로 호출하여 최상위 루트 노드로 설정
- union 함수: 두 집합을 하나로 합치는 역할
- find 함수를 사용하여 노드 x와 노드 y의 루트 노드 찾기
- rootX와 rootY가 다르면, rootY를 rootX의 자식으로 설정하여 두 집합을 하나로 합치기
- costs 리스트:
- [u, v, cost] 형태(u와 v는 연결할 두 섬의 번호이고, cost는 그 사이의 다리를 건설하는 비용)
- 간선들을 비용(cost)을 기준으로 오름차순으로 정렬해 가장 작은 비용의 간선부터 선택할 수 있도록 함
- parent 리스트: 초기 상태에서 각 노드가 자기 자신을 부모로 갖도록 설정(처음에는 모든 섬이 독립된 집합)
- for문: 정렬된 간선들을 순서대로 처리
- 각 간선에 대해, u와 v의 루트가 다르면 (즉, 두 섬이 아직 연결되지 않았다면) 이 간선을 선택\
- union 함수를 호출 -> 두 섬을 하나의 집합으로 합치고, 해당 간선의 비용을 total_cost에 추가
'2024 코딩테스트 스터디' 카테고리의 다른 글
[10주_7일차] 백준-2212 센서(Python) (0) | 2024.08.12 |
---|---|
[10주_6일차] 프로그래머스-단속 카메라(Python) (0) | 2024.08.11 |
[10주_4일차] 프로그래머스-구명보트(Python) (0) | 2024.08.09 |
[10주_3일차] 프로그래머스-큰 수 만들기(Python) (0) | 2024.08.08 |
[10주_2일차] 프로그래머스-조이스틱(Python) (0) | 2024.08.07 |