[프로그래머스 Level3] 섬 연결하기 - 파이썬(Python)

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

프로그래머스

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

4

[[0,1,1], [0,2,2], [1,2,5], [1,3,1], [2,3,8]]

4

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

---

이 문제를 풀며 크루스칼 알고리즘이라는 것에 대해 처음 알게 되었다.

찾아보니 그래프 관련 주요 알고리즘으로 내가 알던 1)다익스트라, 2)플로이드-워셜, 3)벨만 포드 이외에도 4)크루스칼, 5)프림 알고리즘이 있었다.. 1과 2는 익숙해지기 시작하려는데 이제 4를 배우고 3, 5도 나중엔 만날 일이 있겠지.. ㅎㅎㅠㅠ

 

Kruskal Algorithm

 

 

<< 전체 코드 >>

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:x[2]) # 비용을 기준으로 오름차순 정렬
    connect = set([costs[0][0]]) # 간선 연결 정보를 담는 set
    while len(connect) != n:
        for cost in costs:
            if cost[0] in connect and cost[1] in connect: # 사이클 형성을 막음
                continue
            if cost[0] in connect or cost[1] in connect: # 기존 간선과 이어져야 함
                connect.update([cost[0], cost[1]])
                answer += cost[2]
                break
                
    return answer