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

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

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. 위 과정을 반복하면 정답이다

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

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

from http://javaiyagi.tistory.com/646 by ccl(A) rewrite - 2021-11-24 14:27:21