[백준1197] / 최소 스패닝 트리 - MST

 

분명... 알고리즘 수업 때 배웠던.. MST

오래되니 잊어버려서 다시 도전!한 문제~

 

백준1197

 

 

푼 날짜 : 2024.11.08

푼 문제 : [1197] / 최소 스패닝 트리

사용한 언어 : python

알고리즘 : MST(Prim)

 

 

접근 방식 :

Kruskal 이랑 Prim 둘 중 Prim 방식으로 풀었다. 현재 기준으로 가장 비용이 낮은 것으로 이어나가는 방식이다.

(이건 추후 다시 한 번 개념 정리해서 올려야겠다.)

 

heapq를 사용하기 때문에 가장 작은 비용을 꺼내는 것은 쉽다!

방문하지 않은 정점을 찾아나가며 비용이 가장 작은 길을 선택한다.

 

 

 

코드 :

import sys
import heapq

V, E  = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(V+1)]
visited = [0 for _ in range(V+1)]

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    # heapq를 사용하므로 비용을 먼저 넣어주기
    graph[a].append((c, b)) 
    graph[b].append((c, a))


heap = [(0, 1)]
min_cost = 0

while heap:
    n_cost, n_edge = heapq.heappop(heap)

    if not visited[n_edge]:
        min_cost += n_cost
        visited[n_edge] = 1

        for c, e in graph[n_edge]:
            if not visited[e]:
                heapq.heappush(heap, (c, e))

print(min_cost)

 

 

조금씩 풀 수 있는 알고리즘 문제가 는다는 것... 아주 기분 좋은 일!!

성장이 느껴진다 느껴져 ~~~~