[BOJ / 백준] 16562 친구비 (G4 / DFS) - Python

링크

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

 

 

 

 

문제 해석

돈을 주면 친구가 되어 준다.
친구의 친구는 친구다.
가진 돈의 한도 내에서 가장 적은 비용으로 모두와 친구가 될 수 있는 방법을 구하라.


입력
첫 번째 줄 : n m k
  n : 학생 인원 수
  m : 친구 관계 수
  k : 가지고 있는 돈

두 번째 줄 : n명의 학생이 각각 친구비로 원하는 돈

m개의 줄 : f1 f2
  f1 : 친구 1
  f2 : 친구 2
  -> 1, 2는 서로 친구사이


출력
모든 학생을 친구로 만들 수 있으면 최소 비용 출력
친구를 다 사귈 수 없으면 "Oh no" 출력

 

특이사항
친구 숫자는 1부터 시작함

 

 

 

 

풀이 & 코드 해석

연결요소로 이어진 사람들은 한 명만 매수해도 모두 친구가 됩니다.

 

따라서 단지번호 붙이기와 같이 연결 요소를 찾으면 되는 간단한 문제입니다.

 

다만 각 연결 요소에서 가장 친구비가 적게 드는 사람을 구해서 그 사람을 매수해야만 전체 친구비가 줄어들 수 있습니다.

 

 

 

위와 같은 상황에서 1과 3이 묶인 연결 요소를 친구로 만들 떄는 친구 1을 매수하는 것이 친구 3을 매수하는 것이 더 저렴합니다. 

 

 

 

 

코드

import sys
sys.setrecursionlimit(10**7)


def dfs(idx):
    global now_ans

    v[idx] = True

    now_ans = min(now_ans, cost[idx])

    for i in graph[idx]:
        if v[i] == True:
            continue
        dfs(i)


n, m, k = list(map(int, input().split()))

cost = [0]

cost.extend(list(map(int, input().split())))

graph = [[] for _ in range(n + 1)]

for _ in range(m):
    f1, f2 = list(map(int, input().split()))

    graph[f1].append(f2)
    graph[f2].append(f1)

v = [False] * (n + 1)
ans = 0

for i in range(1, n + 1):
    if v[i] == False:
        now_ans = int(1e9)
        dfs(i)
        ans += now_ans

if ans <= k:
    print(ans)
else:
    print("Oh no")

 

 

 

 

발생한 문제 & 해결 방안

python으로 진행 시 재귀 한도를 넘어가기 때문에 설정 코드가 필요합니다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java