[백준] 16562번 - 친구비 (파이썬)

https://www.acmicpc.net/problem/16562

# 친구비
import sys
import heapq
input = sys.stdin.readline
N, M, k = map(int, input().split())
arr = [[]for _ in range(N+1)]
moneys = [0]+list(map(int, input().split()))
for i in range(1, N+1):
    arr[0].append((moneys[i], i))
for _ in range(M):
    a, b = map(int, input().split())
    arr[a].append((0, b))
    arr[b].append((0, a))


def make_friend():
    global answer
    q = []
    heapq.heappush(q, (0, 0))
    visited = [False] * (N+1)
    while q:
        money, node = heapq.heappop(q)
        if not visited[node]:
            visited[node] = True
            answer += money
            if answer > k:
                return False
            for nmoney, nnode in arr[node]:
                if not visited[nnode]:
                    heapq.heappush(q, (nmoney, nnode))
    return True


answer = 0
if make_friend():
    print(answer)
else:
    print('Oh no')

 

MST, 프림
1. 값을 입력받으면서 인접 리스트를 만든다.
2. make_friend : 프림알고리즘
    - 현재 방문한 그래프에서 연결된 간선들 중 가장 작은 값의 노드를 하나씩 포함해 나간다.
    - 현재까지의 합이 소지한 돈보다 크다면 친구 전부 사귀기 실패 return False
3. make_friend의 결광에 따라 answer 출력

 

문제를 보자마자 Union-Find를 생각했지만, 다른 방식으로 풀어보고 싶어서 MST로 접근을 했다.

개인적으로 크루스칼보다 프림 알고리즘을 선호한다.

(가끔 프림으로 풀지 못하는 MST문제도 등장한다. 그때는 크루스칼을 이용했다.)