알고리즘 문제 풀이/프로그래머스

[섬 연결하기/LV3/Python3]

제유찬 2024. 10. 6. 11:42
문제 설명
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