프로그래머스 섬 연결하기 파이썬

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

코딩테스트 연습 - 섬 연결하기

 

크루스칼 알고리즘을 이용하면 쉽고 빠르게 풀 수 있는 문제이다.

 

이 문제를 처음 접했을 때는 크루스칼 알고리즘을 모르고 있었다.

 

크루스칼 알고리즘을 모르는채로 대강 계획을 잡고 풀어보려했는데 생각보다 구현이 잘 안돼서 질문/답변 을 확인하다가 크루스칼 알고리즘을 알게 되었다.

 

import heapq


def get_parent(c, node):
    if c[node] == node:
        return node
    return get_parent(c, c[node])


def union_find(c, edge):
    p1 = get_parent(c, edge[1])
    p2 = get_parent(c, edge[2])

    if not p1 == p2:
        if p1 > p2:
            c[p1] = p2
        else:
            c[p2] = p1

        return edge[0]
    return 0


def solution(n, costs):
    answer = 0
    h = [(cost, node1, node2) for node1, node2, cost in costs]
    heapq.heapify(h)

    c = [x for x in range(n)]

    while h:
        answer += union_find(c, heapq.heappop(h))

    return answer


print(solution(4, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]))

 

이 문제는 크루스칼 알고리즘을 그대로 구현하기만하면 풀리는 문제이다.

 

1. 가장 비용이 작은 순서로 꺼낼 수 있도록 우선순위큐에 담는다.

 

2. 노드와 같은 수를 가지는 싸이클 테이블을 생성한다

 

3. 노드 와 노드를 잇는 간선을 비용이 적은 순서대로 순회하며 각 노드의 부모노드를 확인한다.

 

4. 각 노드의 부모노드가 같다면 그 간선은 이미 서로 연결된 것이므로 연결할 필요가 없다.

 

5. 각 노드의 부모노드가 다르다면 두 간선은 아직 서로 이어지지 않은 상태이므로 두 노드 중 큰 값의 부모노드 번호를 기록하고 비용을 저장한다

 

6. 위 과정을 반복하면 정답이다

 

 

그동안 이런류의 문제를 푸는 알고리즘을 모르고, 막연히 그래프, 노드, 간선 이런 이야기가 나오면 어렵고 불편하다는 인식으로 피해왔는데 알고보니 무척이나 간단하다.

 

말로만 듣던 다익스트라도 별거 아니겠지..?