둔필승총

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

문제 설명

(문제를 다 읽고나서 일단 슬펐다 ㅠㅠ) 준석이는 친구를 사귀기 위해서 친구비를 내야되는데 친구의 친구는 똑같이 준석이의 친구이므로, 만약 A라는 친구를 사귀면 A의 친구들도 모두 준석이의 친구가 되는 논리이다. 그래서 k원이 있을 때 준석이는 모든 친구를 사귈 수 있는지에 대해서 판단하는 문제였다.

문제 해설

먼저 친구들끼리는 이미 연관관계가 있을 것이다. 해당 정보를 graph에 1차원 배열로 정리하였다. (혹시나 2차원으로 정의했을 경우 시간초과에 대비했다)
그리고 친구가 되었는지 아닌지를 판단하기 위해 visited라는 변수를 두었다.
bfs함수를 정의하였다. bfs함수는 시작 노드를 파라미터로 입력받는다.

그리고 bfs를 진행하면서 연결된 모든 노드들을 확인하고 친구비가 최소인 값을 반환한다.

즉, 만약 1번 3번 5번 친구의 친구비가 각각 10,20,30 이고 서로 연결되어있다고 가정하자.

bfs(1)을 넣으면 1,3,5은 visited가 True로 바뀌고 제일 최소값인 10이 반환된다.

(연결된 친구들 정보도 컴파일을 위해 member 집합으로 확인하였다)

그리고 n번 반복해서 해당 노드를 방문하지 않았을 경우 bfs(node값)을 해주면 된다.

그리고 반환값은 최소이므로 해당 값들을 모두 더해준것이 정답이 된다. 그리고 해당 정답이 k보다 크다면 문제에서 주어진대로 Oh no를 출려해주면 된다.

from collections import deque

n, m, k = map(int, input().split())  # 학생 수, 친구관계 수, 가지고 있는 돈
costs = list(map(int, input().split()))  # 친구별 필요한 돈
graph = [[] for _ in range(n)]

for _ in range(m):
    v, w = map(int, input().split())
    graph[v - 1].append(w - 1)
    graph[w - 1].append(v - 1)
temp = [i for i in range(n)]
answers = []
visited = [False for _ in range(n)]

def bfs(start):
    q = deque()
    members = set()
    min_node = 10000
    q.append(start)
    while q:
        x = q.popleft()
        if costs[x] < min_node:
            min_node = costs[x]
        visited[x] = True
        members.add(x)
        for node in graph[x]:
            if not visited[node]:
                q.append(node)
    return min_node
min_cost = 0
for i in range(n):
    if not visited[i]:
        min_cost += bfs(i)
if min_cost > k:
    print("Oh no")
else:
    print(min_cost)