문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
입출력 예
n costs return 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
N개의 섬을 잇는 다리의 최소 비용을 구하는 문제로 요약이 가능하다.
MST 알고리즘 중 하나인 크루스칼 알고리즘을 사용하였다.
현재 선택 가능한 간선 중 최소 비용의 간선을 선택하는 탐욕법에 속하는 알고리즘이다.
구현 시 주의할 점으로는 간선의 개수는 항상 n-1개(최소한의 간선)이며, 사이클이 존재해서는 안된다.
이를 위해 Union_Find 알고리즘을 사용하였다.
재귀호출로 인한 에러를 방지하기 위해 경로 압축과 더불어 재귀 호출 제한을 10^6으로 늘리는 코드를 추가했다.
시간 복잡도는 비용 순으로 정렬을 하였으므로 O(nlogn)이다.
import sys sys.setrecursionlimit(10**6) def solution(n, costs): p = [i for i in range(n)] def find(v): if v == p[v]: return v p[v] = find(p[v]) return p[v] def union(v1, v2): r1, r2 = find(v1), find(v2) p[r1] = r2 costs.sort(key=lambda x:x[2]) result = 0 cnt = 0 for v1, v2, cost in costs: if cnt >= n-1: break if find(v1) == find(v2): continue cnt += 1 union(v1, v2) result += cost return result
'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[상담원 인원/LV3/Python3] (0) | 2024.10.19 |
---|---|
[쿠키 구입/LV4/Python3] (0) | 2024.10.15 |
[도둑질/LV4/Python3] (0) | 2024.10.14 |
[호텔 방 배정/LV4/Python3] (0) | 2024.10.12 |
[야근 지수/LV3/Python3] (0) | 2024.10.09 |