[BOJ] 백준 14950번 문제 풀이 (Python)

1. 문제 풀이

heap과 BFS를 활용하여 문제를 풀었습니다.

• heap: 건설 비용이 작은 순서대로 도로를 반환합니다.
• BFS를 이용해 정복된 도시와 연결된 도로들을 순서대로 탐색합니다. 아직 정복이 되지 않는 도시와 연결된 도로들을 heap에 넣고 이후 반환하는 방식을 통해서 도로 건설 비용을 계산하였습니다.

2. 코드

import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().rstrip()

def bfs():
    result, cnt = 0, 0
    visited = [0] * (n+1)
    visited[1] = 1
    q = []
    for nxt, c in graph[1]:
        heappush(q,(c,nxt))
    while q:
        cost, w = heappop(q)
        if visited[w]: continue
        visited[w] = 1
        result += cost + (cnt * t)
        cnt += 1
        for nxt, c in graph[w]:
            if not visited[nxt]:
                heappush(q,(c, nxt))
    return result

n, m, t = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

print(bfs())