[골드 4] 백준 16562 - 친구비 (파이썬)

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

풀이

• 친구끼리 돈을 모아서 대표 한 명의 친구비만 내면 된다.
• 모든 사람들과 친구가 되려면 각 친구 그룹당 최소 친구비만 내면 된다.
• 이때 전체 친구비가 K원 이하라면 총합을 출력, 초과하면 “Oh no”를 출력

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

친구 관계 입력을 받는다 이때 0-Based Index를 통해서 1씩 빼주고 무방향 그래프로 설정 한다.

visit = [False] * N
total = 0
 
for i in range(N):
    if visit[i]:
        continue
 
    queue.append(i)
    visit[i] = True
    min_cost = A[i]
 
    while queue:
        u = queue.popleft()
 
        for v in adj[u]:
            if not visit[v]:
                queue.append(v)
                visit[v] = True
                min_cost = min(min_cost, A[v])
 
    total += min_cost

방문하지 않은 노드에서 BFS를 시작하여 하나의 친구 그룹을 탐색한다.

이 그룹에서 가장 친구비가 싼 사람을 min_cost로 저장하고 total에 누적한다.

if total <= K:
    print(total)
else:
    print("Oh no")

예산과 비교해서 예산 보다 적은 금액이면 총합을 출력하고, 예싼을 초과하면 Oh no를 출력한다.

시간 복잡도 분석

• O(N + M) → 모든 노드와 간선을 한 번씩만 탐색

코드

# 백준 16562 - 친구비
# 분류 : BFS
 
from collections import deque
 
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
adj = [[] for _ in range(N)]
 
total = 0
for _ in range(M) :
    u, v = map(int, input().split())
    u -= 1
    v-= 1
    adj[u].append(v)
    adj[v].append(u)
 
visit = [False] * N
queue = deque()
 
for i in range(N) :
    if visit[i] :
        continue
 
    queue.append(i)
    visit[i] = True
    min_cost = A[i]
 
    while len(queue) != 0 :
        u = queue.popleft()
 
        for v in adj[u] :
            if not visit[v] :
                queue.append(v)
                visit[v] = True
                min_cost = min(min_cost, A[v])
    
    total += min_cost
 
if total <= K :
    print(total)
else :
    print("Oh no")