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

 

 

나의 풀이

def find_parent(parent, x) :
    if parent[x] != x : # 자기 자신이 아닌 경우, 재귀적으로 부모를 찾으러 감
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_node(parent, a,b) :
    a_parent = find_parent(parent, a)
    b_parent = find_parent(parent, b)
    
    if a_parent == b_parent : # 같은 부모인 경우, 싸이클 생성됨
        return False
    
    elif a_parent < b_parent :
        parent[b_parent] = a_parent # 부모의 부모를 변경
        
    else :
        parent[a_parent] = b_parent
   
    return True
        

def solution(n, costs):
    answer = 0 
    parent = [0] * (n)
    
    for i in range(0, n) : # 부모 노드를 자기 자신으로 초기화
        parent[i] = i
        
    costs.sort(key=lambda item:item[2]) # 비용을 기준으로 오름차순
    print(costs)
    
    for a,b,cost in costs : # 작은 비용의 간선부터 합치기, 단 싸이클이 생성될 경우 합치지 않는다
        if union_node(parent, a, b) :
            answer += cost
    print(parent)
    
    return answer

N개의 도시가 존재할 때 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결되게 도로를 설치하는 경우의 문제에선 크루스칼 알고리즘을 사용한다. 

크루스칼 알고리즘은 대표적인 그리디 알고리즘이다.

1. 간선 데이터들 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인한다.
   1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대해 2번의 과정을 반복한다.

 

최종적으로 최소 신장 트리의 간선 개수는 노드의 개수 - 1개가 될 것이다. 

즉, 크루스칼 알고리즘의 핵심 원리는 가장 가중치가 짧은 간선부터 차례로 집합에 추가(Union)하는 것이다.

이때 사이클을 발생시키는 간선은 제외하고 연결한다.

이렇게 하면 항상 최적의 해를 보장한다!