16562 친구비 dfs

골3

지금 진행하고 있는 알고리즘 스터디에서 당일 풀어야 했던 문제였다.

스택 큐 주제를 가지고 진행했던 문제이고, 문제 발제자가 dfs로 해결할 수 있는 문제이다 보니 stack을 적용해서 푸는 것이라고 생각했던 것 같다.

하지만 해당 문제는 스택을 이용하기 보단 인접리스트를 통해 친구 관계의 그룹화를 짓는 것이 문제의 키 포인트였다.

이 정도면 일반적인 dfs 문제지만 약간 응용해서 친구 관계의 그룹에서 최소 비용을 들일 수 있는 노드를 찾아야 했던 것이 문제 난이도를 높이는 요인이었다.

실제로 나도 그냥 dfs를 돌리면서 시작 노드의 비용만 저장해서 한 번 틀렸었다.

문제풀이

1. 모든 친구관계를 순회하기 시작한다.
2. 해당 친구관계와 연결되는 노드를 dfs를 통해 탐색한다.
3. dfs를 통해 탐색하면서 연결되는 친구 비용의 최소값을 갱신해 나간다.
4. 모든 순회를 마치고 배열의 모든 합을 구해서 k보다 작으면 그 값을 출력하고 k보다 크면 비용을 지불할 수 없다는 뜻이므로 Oh no를 출력한다.

import sys
sys.setrecursionlimit(5000)

N, M, k = map(int, input().split(" "))
expense = list(map(int, input().split(" ")))
visited = [False] * (N+1)
MIN = 0
relationship = [[] for _ in range(N+1)]
min_expense = [0] * (N+1)
payment = 0

for _ in range(M):
    a, b = map(int, input().split(" "))
    relationship[a].append(b)
    relationship[b].append(a)

def solution():
    global payment, MIN

    for i in range(1, N+1):
        if not visited[i]:
            visited[i] = True
            MIN = int(1e9)
            dfs(i)
            min_expense[i] = MIN
    if sum(min_expense) > k:
        print("Oh no")
    else:
        print(sum(min_expense))


def dfs(node):
    global MIN
    MIN = min(MIN, expense[node-1])

    for i in relationship[node]:
        if not visited[i]:
            visited[i] = True
            dfs(i)
    return


solution()