프로그래머스(programmers) 섬 연결하기 python 정답 [Greedy Algorithm]

프로그래머스(programmers) 섬 연결하기 python 정답 [Greedy Algorithm]

문제 링크

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

프로그래머스

---

문제 정답

입출력 예시

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

해당 이미지 결과

정답 코드

def solution(n, costs):
    # 특정 원소가 속한 집합을 찾기
    def find(x):
        # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        return find(parent[x]) if parent[x] != x else x
    # 두 원소가 속한 집합을 합치기
    def union(a, b):
        a,b = find(a),find(b)
        // 값이 작은 요소를 부모로
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    answer = 0
    parent = [i for i in range(n)]
    sorted_costs = sorted(costs, key=lambda x : x[2])
    for start,end,cost in sorted_costs:
        if find(start) != find(end):
            union(start,end)
            answer +=cost            

    return answer

---

문제 해설

전형적인 mst 알고리즘으로,

크루스칼 알고리즘이나 프림 알고리즘 둘 중 하나를 선택해섬 문제를 해결하면 된다.

프림 알고리즘은 너무나도 흔하 사용하는 bfs 그래프 순회를 간선 가중치를 더하는 방식으로 구현하기만 하면 된다.

본인은 훈련용으로 크루스칼을 사용하였다

 

이 알고리즘은 정렬이 비용이 가장 비싸기 때문에 O(ElogE)가 된다. (간선의 갯수 E = 최대 V^2 > ElogV)

라고 여러 게시물들에서 설명하는데... 사실 조금만 생각해봐도 저 알고리즘 대로 구현하면 find가 최대 시간복잡도가 V가 나오기 때문에 

순회랑 곱하면 EV가 된다.

(참고 : 서로소 집합 자료 구조)

 

따라서 find 알고리즘을 아래와 같이 바꿔주면 ElogE라 할 수 있다

def find(x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find(parent[x])
        return parent[x]
    else :
        return x

이게 귀찮으면 그냥 프림 쓰면 된다. 프림은 진짜로 elogv가 된다.

알고리즘 구조 상 동일 간선은 양방향으로 2번 밖에 방문할 수 없게 된다.

그리고 정점은 중복 방문 2번으로 2V이다. (갈때 올떄)

참고

https://deep-learning-study.tistory.com/595

[알고리즘] 프림 알고리즘(Prim Algorithm)

Kruskal-Algorithm

[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm)