[Python] 백준 16562번 : 친구비

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

 

난이도: G4

---

문제

---

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

---

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.

출력

---

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

예제 입력

5 3 20
10 10 20 20 30
1 3
2 4
5 4

예제 출력

20

풀이

---

1. 해당 문제는 그래프 문제다. 모든 친구들을 최소비용으로 만나야 하는데, 특정 친구를 돈주고 친구 관계를 만들 시, 해당 친구와 연결된 모든 친구들도 친구 관계가 된다.

2. 그렇다면, 친구들간의 연결그래프를 찾아, 연결그래프중 최솟값을 찾고, 모든 연결그래프들의 최소값을 더하면 모든 친구와 친구 관계를 맺는 가격이 나온다.

3. 해당 방법을 위해 DFS를 이용해 탐색을 하며 visit에 해당 연결그래프의 idx를 넣고, idx번 연결그래프의 최솟값을 group_min_price에 갱신해준다.

4. 탐색이 완전히 끝나면 group_min_price 딕셔너리의 values의 합을 구하고, 이를 가지고 있는 돈 k와 비교하여 정답을 출력한다.

 

※주의사항

모든 친구가 선형 그래프로 이루어 질 시, 재귀함수의 호출값은 10000이 나오는데 python의 기본 재귀함수 호출 최대값은 1000이므로 sys.setrecursionlimit을 통해 확장시켜준다.

제출코드

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**4)
N,M,K=map(int,input().split())
price=[0]+list(map(int,input().split()))

def func(x,idx):
    global price,visit
    for i in graph[x]:
        if not visit[i]:
            visit[i]=idx
            group_min_price[idx]=min(group_min_price[idx],price[i])
            func(i,idx)

graph=[set() for _ in range(N+1)]
visit=[0]*(N+1)
group_min_price={}
for _ in range(M):
    v,w=map(int,input().split())
    graph[v].add(w)
    graph[w].add(v)

idx=1
for i in range(1,N+1):
    if not visit[i]:
        visit[i]=idx
        group_min_price[idx]=price[i]
        func(i,idx)
        idx+=1

res=sum([i for i in group_min_price.values()])
print(res if res<=K else "Oh no")