[백준/파이썬] 16562 친구비

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

 

📝 문제 요약

• 학생 N명과 친구 관계 M개, 각 학생마다 친구비가 있음
• 친구의 친구도 친구이므로, 한 그룹에 속한 사람은 한 번만 친구비를 내면 됨
• 예산 K원 안에서 모든 학생과 친구가 될 수 있는지 판단하고, 가능하면 최소 비용 출력, 불가능하면 Oh no 출력

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n,m,k = map(int, input().split())
A = [0] + list(map(int, input().split())) # 1번 인덱스를 맞추기 위함

friends = [[] for _ in range(n+1)]

for _ in range(m):
    v,w = map(int, input().split())
    friends[v].append(w)
    friends[w].append(v)

visited = [False] * (n+1) # 친구 사이 Y/N
answer = 0

def dfs(x):
    visited[x] = True
    min_cost = A[x]
    for f in friends[x]:
        if not visited[f]:
            min_cost = min(min_cost, dfs(f))
    return min_cost


for i in range(1, n+1):
    if not visited[i]:
        answer += dfs(i)

if k >= answer:
    print(answer)
else:
    print("Oh no")

 

✅ friends = [[] for _ in range(n+1)] 
 -  2차원 리스트를 만들 때는 list comprehension으로 새 객체를 생성해야 함

 - friends = [[]] * (n+1) 는 얕은 복사 문제로 모든 요소가 같은 리스트 객체를 가리켜 모든 리스트에 같이 들어감

 

🧠 핵심 아이디어

1. 학생들을 그래프의 노드, 친구 관계를 간선으로 표현
2. DFS/BFS를 통해 **한 연결 요소(친구 그룹)**를 한 번에 탐색
3. 그룹 내에서 가장 저렴한 친구비만 골라서 합산