[백준 20303번] 파이썬 - 할로윈의 양아치

백준 20303_할로윈의 양아치

시간 제한 1초, 메모리 제한 1024MB

# 조건

• 10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다.
• 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다.
• 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.
• 단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다.
• 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다.
• 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)
• 사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다.
• 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.
• 스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다.
• 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

입력

• 첫째 줄에 정수 N, M, K가 주어진다.
• N은 거리에 있는 아이들의 수, M은 아이들의 친구 관계 수, K는 울음 소리가 공명하기 위한 최소 아이의 수이다. (1<=N<=30,000, 0<=M<=100,000, 1<=K<=MIN(N, 3000))
• 둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 C1, C2, C3 ... 이 주어진다. (1<=Ci<=10,000)
• 셋째 줄부터 M개 줄에 걸쳐 각각의 줄에 정수 a, b가 주어진다. 이는 a와 b가 친구임을 의미한다.
• 같은 친구 관계가 두 번 주어지는 경우는 없다.(1<=a, b<=N, a != b)

출력

• 스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

# 접근 방법

• 처음에 입력을 받은 후, 친구 관계를 union, find 함수를 통하여 기록해준다.
  • 번호가 작은 친구를 기준으로 기록해둔다.
  • 예) 1, 3, 5번이 서로 친구라면 [1, 2, 1, 4, 1] 과 같이 기록
• parents 배열에 친구 관계가 기록되었다면, 이후 해당 번호의 아이가 친구가 몇 명인지, 그 그룹의 사탕의 수가 몇 개인지 더해준다.
  • 작은 번호의 친구를 기준으로 하였으므로, parents 배열의 값이 아이의 번호와 같지 않은 친구가 root이다.
  • 따라서, root 번호의 친구 값에 이어진 친구의 수, 사탕의 총 합을 기록해나간다.
• 냅색 알고리즘을 활용해줄 dp 배열을 만들어 준 후, 최대로 뺏을 수 있는 사탕의 수를 갱신해나간다.
  • dp는 뺏을 수 있는 최대 인원 수 크기로 만들어 준다.
  • 이후 사탕을 뺏을 수 없으면 위의 값을 그대로 가져오고
  • 뺏을 수 있다면, 최대 값을 비교하여 갱신해준다.
• 최대 뺏을 수 있는 아이의 수부터, 현재 뺏는 친구 그룹의 수까지 내려가며 최댓값을 갱신해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

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

def union(x, y):  
    x = find(x)  
    y = find(y)  
    if x < y:  
        x, y = y, x  
    parents[x] = y  


def robbing():  
    for i in range(1, N+1):  
        if i != parents[i]:  
            continue  
        for j in range(K-1, cnt_friends[i]-1, -1):  
            dp[j] = max(dp[j], dp[j-cnt_friends[i]] + candies[i])  

N, M, K = map(int, input().split())  
candies = [0] + [*map(int, input().split())]  
parents = [i for i in range(N+1)]  
cnt_friends = [1] * (N+1)  

for i in range(M):  
    a, b = map(int, input().split())  
    union(a, b)  

for k in range(1, N+1):  
    if k != parents[k]:  
        root = find(k)  
        candies[root] += candies[k]  
        cnt_friends[root] += cnt_friends[k]  

dp = [0 for _ in range(K)]  
robbing()  
print(max(dp))