백준 16562번 파이썬 문제풀이(친구비)

---

해당 문제는 연결요소의 개수가 몇개있냐 그리고 연결요소의 리스트들을 저장해놓고 그 중 가작 적은 금액을 요구하는 학생들을 구하라는 문제이다. well-known 문제이며 간단히 dfs로 구현 가능하다.

 

import sys

sys.setrecursionlimit(3000)

N, M, K = map(int, input().split())
wanted = [0] + list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (N + 1)
friends = []  # 친구 관계를 담을 리스트(A무리 , B무리 .. 식으로 담음)


# DFS를 돌면서 연결요소 즉 친구무리가 몇개 있는지 확인
def dfs(v, arr):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            arr.append(i)
            dfs(i, arr)


# DFS를 1~N 번까지 돈다.
for i in range(1, N + 1):
    if not visited[i]:
        arr = [i]
        visited[i] = True
        dfs(i, arr)
        friends.append(arr)

result = 0
# 친구무리중 가장 적은 금액을 result에 계속 더해준다.
for friend in friends:
    cost = 1 << 60
    for j in friend:
        if cost > wanted[j]:
            cost = wanted[j]
    result += cost

# 만약 그 값이 가지고 있는 돈보다 적다면
if result <= K:
    print(result)
else:
    print("Oh no")

 

2. Union Find로도 풀이가 가능하다

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)


def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]


def union_(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return

    parent[a] = b
    cost[b] = min(cost[a], cost[b])


N, M, K = map(int, input().split())

parent = [i for i in range(N + 1)]

arr = [0] + list(map(int, input().split()))
cost = arr[:]
for _ in range(M):
    a, b = map(int, input().split())
    union_(a, b)

ans = 0

for i in range(1, N + 1):
    if parent[i] == i:
        ans += cost[i]

if ans > K:
    print('Oh no')
else:
    print(ans)