프로그래머스, 섬 연결하기
🪴 문제
https://school.programmers.co.kr/learn/courses/30/lessons/42861
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🪴풀이
모든 노드를 방문한다.
최소 비용으로 통행하고자 한다.
최소신장 트리 문제이다.
프림 알고리즘, 크루스칼 알고리즘
🪴프림 알고리즘
어떠한 노드에서 출발해도 상관없다. 왜냐하면, 결국 모든 노드를 이어줄 것이기 때문!
우선순위 큐 자료구조를 이용해 최소 비용으로 갈 수 있는 모든 간선 정보를 비교해 방문한 적 없는 노드를 방문한다.
노드 수 n개, 간선수 N=len(costs)
O((n + N) log n) 의 시간 복잡도를 가진다.
최대 n은 100이고, 양방향 트리이므로 n(n-1)/2개 최대 간선을 가질 수 있다. 따라서 100*99/2 = 4950이 최대 N이라고 할 수 있다.

3번 노드에서는 최소 비용 간선이 pop되므로 계산이 되지 않을 뿐 1번노드 다시 방문해 최소 비용 간선을 찾아준다.
import heapq
from collections import defaultdict
def solution(n, costs):
# 최소신장트리, 프림 알고리즘 이용
# 우선순위 큐 활용.
adj = defaultdict(list)
for node1, node2, cost in costs:
adj[node1].append((cost, node2))
adj[node2].append((cost, node1))
visit = [False]*n
# 모든 노드를 탐색하니 0~(n-1)노드 중 아무데서나 시작해도 무관
heap = [(0,0)] # cost, startNode
totalCost = 0
while heap:
curCost, curNode = heapq.heappop(heap)
if not visit[curNode]:
visit[curNode] = True
totalCost+=curCost
# 다음에 갈 수 있는 모든 간선 정보 우선순위 큐에 넣어주기.
for nextCost, nextNode in adj[curNode]:
heapq.heappush(heap, (nextCost, nextNode))
return totalCost
🪴 크루스칼 알고리즘
비용 순으로 정렬한 뒤, 비용이 가장 적게 드는 간선먼저 연결한다.
그래서 간선을 정렬하는데 N = len(costs), O(N log N) 정도의 시간 복잡도을 가진다.
혹시, 유니온파인드 알고리즘을 들어본적이 있는가?
부모찾기! 부모가 동일하면 최소 신장이 될 수 없으므로 비용을 계산하지 않고 넘어간다.
탐색하는데 O(N)
대략 N log N + N = O(N log N) 시간 복잡도.
최대 n은 100이고, 양방향 트리이므로 n(n-1)/2개 최대 간선을 가질 수 있다. 따라서 100*99/2 = 4950이 최대 N이라고 할 수 있다.

최소 비용 순으로 for문을 돌면서 cycle이 생기지 않을 경우에만 비용을 더해준다.
from collections import defaultdict
def find(node):
global parent
if parent[node] != node:
return find(parent[node])
return node
def union(node1, node2):
global parent
root1 = find(node1)
root2 = find(node2)
if root1 < root2:
parent[root2] = root1
else:
parent[root1] = root2
def solution(n, costs):
# 최소 신장트리
# 크루스칼 알고리즘
# 초기 부모 정보
global parent
parent = list(range(n))
# 비용 순으로 정렬
costs = sorted(costs, key=lambda x:x[2])
totalCost = 0
for node1, node2, cost in costs:
if find(node1) != find(node2):
union(node1, node2)
totalCost+=cost
return totalCost
'알고리즘' 카테고리의 다른 글
백준, 효율적인 해킹 (1) | 2023.11.26 |
---|---|
백준, 단지 번호 붙이기 (0) | 2023.11.22 |
프로그래머스, 표현 가능한 이진 트리 (0) | 2023.10.25 |
백준 17406 배열 돌리기 4 (1) | 2023.10.23 |
백준, 사다리 조작(combinations 활용) (0) | 2023.10.13 |