[프로그래머스] Level3 : 섬 연결하기 (파이썬)

MST 문제

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

프로그래머스

---

💡풀이코드 (성공 - MST Kruskal)

def solution(n, costs):
    answer = []
    graph = []
    ans = 0
    
    for n1, n2, w in costs:
        graph.append((w, n1, n2))
    parent = [0] * (n + 1)
    
    def init():
        for i in range(1, n + 1):
            parent[i] = i
    
    def find(i):
        while parent[i] != i:
            parent[i] = parent[parent[i]]
            i = parent[i]
        return i
    
    def merge(i, j):
        ii = find(i)
        jj = find(j)
        
        if ii != jj:
            parent[ii] = jj
    
    graph.sort()
    
    init()
    for w, u, v in graph:
        p = find(u)
        q = find(v)
        
        if find(p) != find(q):
            merge(p, q)
            answer.append(w)
    
    ans = sum(answer[:n-1]) # 노드의 갯수 : n-1
    print(answer)
    print(ans)
    
    
    return ans

 

💡풀이코드 (성공 - MST Prim)

import heapq

def solution(n, costs):
    answer = 0
    
    graph = [[] for _ in range(n)]
    
    for u, v, w in costs:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    visited = [False] * n
    print(visited)
    heap = []
    heapq.heappush(heap, (0, 0))
    ans = []
    
    while heap:
        w, u = heapq.heappop(heap)
        
        if visited[u] == False:
            visited[u] = True
            ans.append(w)
        
            for i, weight in graph[u]:
                if visited[i] == False:
                    heapq.heappush(heap, (weight, i))
    answer=  sum(ans)
        
        
        
    
    
    return answer