# 전력난
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 출력
'Algorithm > BOJ' 카테고리의 다른 글
[백준] 17299번 - 오등큰수 (파이썬) (0) | 2022.03.14 |
---|---|
[백준] 17298번 - 오큰수 (파이썬) (0) | 2022.03.14 |
[백준] 19236번 - 청소년 상어 (파이썬) (0) | 2022.03.12 |
[백준] 10282번 - 해킹 (파이썬) (0) | 2022.03.11 |
[백준] 2473번 - 세 용액 (파이썬) (0) | 2022.03.10 |