[백준] 16562번 친구비 파이썬 코드

코드1 (dfs)

n,m,k = map(int, input().split())
money = [0,*map(int, input().split())]
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
for _ in range(m):
  x,y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

moneylist = []

def dfs(a, graph, visited):
  stack = [a]
  visited[a] = 1
  cost = money[a]
  while stack:
    pn = stack.pop()
    for i in graph[pn]:
      if not visited[i]:
        visited[i] = 1
        cost = min(cost, money[i])
        stack.append(i)
  moneylist.append(cost)

for i in range(1,n+1):
  if not visited[i]:
    dfs(i, graph, visited)
print(sum(moneylist)) if sum(moneylist) <= k else print("Oh no")

 

코드2 (유니온 파인드)

import sys
sys.setrecursionlimit(10**5)

def find(a, lst):
  if a != lst[a]:
    lst[a] = find(lst[a], lst)
  return lst[a]

def union(a,b,lst):
  a = find(a, lst)
  b = find(b, lst)
  
  if a < b:
    lst[b] = a
  else:
    lst[a] = b
  money[a],money[b] = min(money[a],money[b]), min(money[a],money[b])
  # 더 적은 돈으로 업데이트
    
n,m,k = map(int, input().split())
money = [0, *map(int, input().split())]
parent = [i for i in range(n+1)]
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y,parent)

cost = 0
for i in range(1, n+1):
  if parent[i] == i:
    cost += money[i]

print(cost) if cost <= k else print("Oh no")

분리 집합으로 해결하기가 조금 더 까다로웠던 문제였다.