[파이썬] 프로그래머스 : 섬 연결하기 (Lv.3)

[파이썬] 프로그래머스 : 섬 연결하기 (Lv.3)

 

프로그래머스

---

풀이

0. 방향성 생각

최소 비용으로 모든 섬을 연결하는 문제. 최소 스패닝 트리랑 같은 맥락이다.

1. 함수 작성

def solution(n,costs):
    costs.sort(key=lambda x:x[2])
    parent = [i for i in range(n+1)]
    
    def find_parent(parent,x):
        if parent[x] != x:
            parent[x] = find_parent(parent,parent[x])
        return parent[x]
    
    def union_parent(parent,x,y):
        x = find_parent(parent,x)
        y = find_parent(parent,y)
        if x < y:
            parent[y] = x
        else :
            parent[x] = y

문제의 입력에서 (노드a,노드b,가중치) 형태로 입력이 주어져있다.

가중치가 작은 순으로 정렬해준다. 또한 parent를 만들어서 자기 자신을 가르키게 초기화해준다.

 

2. MST 진행

    min_cost = 0
    for (a,b,cost) in costs:
        if find_parent(parent,a) != find_parent(parent,b):
            union_parent(parent,a,b)
            min_cost += cost
                
    return min_cost

노드 a와 노드b의 부모가 다르다면(서로 다리로 연결돼있지 않으면), 다리를 연결하고 부모를 가장 작은 노드로 업데이트한다. 또한 연결할 때 사용된 가중치를 얻는다.

 

---

전체코드

def solution(n,costs):
    costs.sort(key=lambda x:x[2])
    parent = [i for i in range(n+1)]
    
    def find_parent(parent,x):
        if parent[x] != x:
            parent[x] = find_parent(parent,parent[x])
        return parent[x]
    
    def union_parent(parent,x,y):
        x = find_parent(parent,x)
        y = find_parent(parent,y)
        if x < y:
            parent[y] = x
        else :
            parent[x] = y
            
    min_cost = 0
    for (a,b,cost) in costs:
        if find_parent(parent,a) != find_parent(parent,b):
            union_parent(parent,a,b)
            min_cost += cost
                
    return min_cost