[Python - 프로그래머스] 코딩테스트 연습 > 탐욕법(Greedy) > 섬 연결하기

[Python - 프로그래머스] 코딩테스트 연습 > 탐욕법(Greedy) > 섬 연결하기

 

 

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

프로그래머스

 

---

Solution

 

def solution(n, costs):
    # cost가 작은 기준으로 sort
    costs.sort(key = lambda x:x[2])
    print(costs)
 
    # 가장 cost가 작은 거 부터 시작
    bridge = list()
    bridge.append(costs.pop(0))
 
    while len(costs) > 0 :
        candidate = costs.pop(0)
 
        s = set(bridge[0][:2])
        _ = [s.update(v[:2]) for _ in bridge for v in bridge if set(v[:2]) & s]
 
        if len(set(candidate[:2]) - s) > 0 :
            bridge.append(candidate)
    
    return sum([i[2] for i in bridge])

 

탐욕법이라는 주제에 맞도록 풀었다.

주어진 costs를 비용 기준으로 오름차순 sorting하고 가장 비용이 작은 것부터 연결을 시작한다.

 

sorting 순서대로 연결하는데, 연결하기 전에 해당 섬이 이미 연결할 수 있는지 없는지 확인한다.

이미 연결할 수 있으면 넘어가고 연결할 수 없을 때만 연결한다.

연결한 섬들은 bridge에 저장한다.

 

s = set(bridge[0][:2])

_ = [s.update(v[:2]) for _ in bridge for v in bridge if set(v[:2]) & s]

에서 s가 현재 bridge로 연결 가능한 섬들 목록이다.

이 부분은 이전 포스팅 중 다른 사람의 풀이를 참고했으머, 설명도 해당 포스팅에 있다.

 

---

다른 사람의 풀이

 

 

크루스칼 알고리즘 또는 최소신장트리(Minimum Spanning Tree, MST) 라고 한다.

ancestor을 통해 두 섬이 연결되어있는지 확인한다.

 

예를 들어 n=5이고 현재 parents가 [2, 2, 3, 3, 4]라고 해보자.

 

0번째 노드의 조상은 3이다.

ancestor(0, parents)의 결과를 보면 되는데,

parents[0] = 2 -> parents[2] = 3 -> parents[3] = 3 이므로 3이다.

 

1번째 노드의 조상도 3이다.

마찬가지로 ancestor(1, parents)의 결과가 3이다.

parents[1] = 2 -> parents[2] = 3 -> parents[3] = 3 

 

즉, 0번째 노드와 1번째 노드의 조상이 같으므로 둘은 어떤 루트로든 연결할 수 있다는 것을 의미한다.

 

parents는 말 그대로 부모를 나타내는 list이며, ancestor는 부모를 넘어 조상을 return하는 function이다.

 

 

다음의 예시를 통해 전체 과정을 알아보자.

 

n = 5
costs = [[0, 1, 2], [0, 2, 1], [1, 3, 3], [1, 2, 1], [2, 4, 10]]

 

 

 

 

costs를 비용 오름차순으로 sorting하고 

아직은 아무것도 연결되어있지 않으니 parents도 그냥 range로 초기화시킨다.

 

 

answer이 최종 필요한 비용들의 합이 될 것이고, bridges로는 섬 전체가 연결되었는지를 확인한다.(bridges가 n-1개면 섬 전체 연결)

 

 

edges를 for문으로 하나씩 확인하면서 연결이 필요하면 연결하고, 필요없으면 연결하지 않는다.

위에서 살펴보았던 ancestor로 두 섬이 연결되어있는지를 확인한다.

두 섬의 조상이 같으면 연결된 것이고, 다르면 연결되지 않은 것이니 연결한다.

연결하면서 드는 비용은 answer에 더해주고, 다리가 하나 더 연결되었으니 bridges도 1 더해준다.

 

마찬가지로 parents도 update하는데, 이제 섬1에서 섬2에 도달할 수 있으므로 섬1의 조상을 섬2로 update한다.