Programmers / 3단계 / 섬 연결하기 / python / Greedy / Kruskal 알고리즘

 

https://school.programmers.co.kr/learn/courses/30/lessons/42861

 

 

코드

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2])
    s = set([costs[0][0]])
    
    while len(s) != n:
        for v in costs:
            if v[0] in s and v[1] in s:
                continue
            if v[0] in s or v[1] in s:
                s.update([v[0], v[1]])
                answer += v[2]
                break
    return answer

 

kruskal 알고리즘을 사용해 문제를 해결할 수 있다. 

kruskal 알고리즘이란 최소한의 비용으로 구성되는 신장 트리인 최소 신장 트리의 대표적인 알고리즘으로 그리디 알고리즘으로 분류된다. 

 

동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 

  2-1. 사이클이 발생 X → 최소 신장 트리에 포함시킴

  2-2. 사이클이 발생 → 최소 신장 트리에 포함시키지 않음

3. 모든 간선에 대해 2번의 과정 반복

 

 

참조

[Python] 코딩테스트 유형 - 10-2. 최소 신장 트리(MST), Kruskal 알고리즘 (velog.io)

[Python] 코딩테스트 유형 - 10-2. 최소 신장 트리(MST), Kruskal 알고리즘