[백준] 6497번 - 전력난 (파이썬)

acmicpc.net/problem/6497

# 전력난
import heapq
import sys
input = sys.stdin.readline


def prim(road_info, house, start):
    result = 0
    q = []
    heapq.heappush(q, (0, start))
    visited = [False] * house
    while q:
        cost, home = heapq.heappop(q)
        if visited[home]:
            continue
        result += cost
        visited[home] = True
        for ncost, nhome in road_info[home]:
            if not visited[nhome]:
                heapq.heappush(q, (ncost, nhome))
    return result


while True:
    house, road = map(int, input().split())
    if house == 0 and road == 0:
        break

    total_cost = 0
    road_info = [[] for _ in range(house)]
    for _ in range(road):
        x, y, cost = map(int, input().split())
        road_info[x].append((cost, y))
        road_info[y].append((cost, x))
        total_cost += cost

    result = prim(road_info, house, 0)
    print(total_cost - result)

 

MST, 프림

1. house, road를 입력을 받는다 (둘 다 0이면 종료)

2. 양방향인 도로의 정보를 입력받으면서 전체 비용을 구한다.

3. 프림알고리즘(MST)

   - 현재 노드들과 연결되어 있는 모든 도로의 값을 heap에 push

   - 가장 작은 비용의 도로를 pop하고, 비용을 누적,  연결된 노드를 방문처리

   - 반복, return result

4. 전체 비용 - result 출력