📌 프로그래머스 - 섬 연결하기

처음에 다익스트라 알고리즘으로 풀었다가 테스트케이스 1,2,6번 뻬고 통과를 못해서 계속 고민하다가 결국 구글링의 힘을 빌렸다.

알고보니 그리디 알고리즘 중 하나인 Kruskal(크루스칼) 알고리즘 을 사용하면 쉽게 풀리는 문제였다..!

굵직한 알고리즘은 얼추 다 풀어봤다고 생각했는데 갈 길이 멀다는 것을 느꼈다.

크루스칼 알고리즘을 이해하기 위해서는 우선 최소신장트리(Mnimum Spanning Tree) 를 알고 있으면 좋다.

최소 신장 트리(Mnimum Spanning Tree,MST)

신장 트리 : 그래프 내부의 모든 노드가 연결되어 있으며 사이클이 없는(트리의 속성) 그래프

최소 신장 트리(MST) : 간선의 가중치 합이 가장 작은 경로로 이루어진 신장트리

Kruskal 알고리즘

모든 node를 가장 적은 비용(cost)으로 연결하기 위한 알고리즘
최소 신장 트리 알고리즘의 대표적인 알고리즘이다.

1. 모든 간선 정보(연결된 정보)를 cost 오름차순으로 정리한다.
2. 작은 cost를 가진 간선부터 연결하면서 진행하여 최소 신장 트리(MST)를 구한다.

📋 내 답안

def solution(n, costs):
    answer = 0
    
    # cost기준으로 낮은 것부터 정렬
    costs.sort(key = lambda x:x[2])
    
    # 연결 확인 용도
    graph = set([costs[0][0]])
    
    while len(graph) < n:
        for i,j,c in costs:
        	# 이미 최소 비용으로 연결되어 있으면 건너 뜀
            if i in graph and j in graph:
                continue
            # 둘 중 하나만 graph에 있으면(연결 안되어있으면)
            if i in graph or j in graph:
                # 여러 개의 값을 넣을 때는 update, 하나는 add
                graph.update([i,j])
                answer += c
                break
                
    return answer