[Python] 16562 친구비

[Gold IV] 친구비 - 16562 

[문제 링크](https://www.acmicpc.net/problem/16562)

---

💻 문제 정의

현재 가진 비용으로 친구들에게 친구비를 주면서 친구 관계를 맺는다고 할 때, 최소 비용으로 모든 친구와 친구할 수 있도록 구하여라.

💡 접근 및 설계

BFS 또는 DFS 그래프 탐색을 통해 친구 그룹을 생성한다. 각 그룹 중에 최소 비용으로 친구를 맺는다면 최소 비용으로 모든 친구와 친구를 맺을 수 있을거라 생각하였다.

✏️ 알고리즘 풀이

def bfs(n):
    Q = deque()
    Q.append(n)
    visited[n] = True

    lst = [n]
    while Q:
        c = Q.popleft()

        for ix in graph[c]:
            if not visited[ix]:
                visited[ix] = True
                Q.append(ix)
                lst.append(ix)

    return lst
    
res = []
for i in range(1, N+1):
    if not visited[i]:
        res.append(bfs(i))

BFS를 이용하여 친구 그룹을 구하였다. 친구 관계가 그래프로 주어질 것이고, 모든 노드에서 방문하지 않은 노드에서 BFS를 시작하여 lst 친구 그룹을 반환한다. 이후 res에 저장한다.

costs = 0
for r in res:
    cost = 10_000_001
    for ix in r:
        cost = min(cost, A[ix])
    costs += cost

print(costs if costs <= K else "Oh no")

각 그룹중에서 친구비가 최소인 친구와 친구를 맺도록 한다. 그때의 비용을 찾아 costs에 업데이트 해준다. 최종적으로 비용이 현재 가진 돈 보다 작다면 최소 비용일 것이고, 넘어간다면 Oh no를 출력한다.

🗒️ 최종 제출 코드

# 16562 친구비

from collections import deque

def bfs(n):
    Q = deque()
    Q.append(n)
    visited[n] = True

    lst = [n]
    while Q:
        c = Q.popleft()

        for ix in graph[c]:
            if not visited[ix]:
                visited[ix] = True
                Q.append(ix)
                lst.append(ix)

    return lst

N, M, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

graph = [[] for _ in range(N+1)]
for _ in range(M):
    v, w = map(int, input().split())
    graph[v].append(w)
    graph[w].append(v)

visited = [False] * (N+1)

res = []
for i in range(1, N+1):
    if not visited[i]:
        res.append(bfs(i))

costs = 0
for r in res:
    cost = 10_000_001
    for ix in r:
        cost = min(cost, A[ix])
    costs += cost

print(costs if costs <= K else "Oh no")

---

💭 오늘의 회고

-