프로그래머스, 섬 연결하기

프로그래머스, 섬 연결하기

 

🪴 문제

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

프로그래머스

 

 

 🪴풀이

모든 노드를 방문한다.

최소 비용으로 통행하고자 한다.

최소신장 트리 문제이다.

프림 알고리즘, 크루스칼 알고리즘

 

 🪴프림 알고리즘

어떠한 노드에서 출발해도 상관없다. 왜냐하면, 결국 모든 노드를 이어줄 것이기 때문!

우선순위 큐 자료구조를 이용해 최소 비용으로 갈 수 있는 모든 간선 정보를 비교해 방문한 적 없는 노드를 방문한다.

 

노드 수 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