[백준/20303] 할로윈의 양아치 (Python)

Problem : https://www.acmicpc.net/problem/20303

20303번: 할로윈의 양아치

 

Difficulty : Gold 3

 

Status : Solved (pypy3)

 

Time : 00:12:33

 

---

 

문제 설명

 

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

 

입력 및 출력

 

입력

 

첫째 줄에 정수 N, M, K가 주어진다. N은 거리에 있는 아이들의 수, M은 아이들의 친구 관계 수, K는 울음소리가 공명하기 위한 최소 아이의 수이다. ( 1 <= N <= 30000, 1 <= M <= 100000, 1 <= K <= min(N, 3000)

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 c1, c2, ..., cn이 주어진다. (1 <= ci <= 10000)

셋째 줄부터 M개 줄에 갈쳐 각각의 줄에 정수 a, b가 주어진다. 이는 a와 b가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (1 <= a, b <= N, a != b)

 

출력

 

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

 

입력 예시

 

10 6 6
9 15 4 4 1 5 19 14 20 5
1 3
2 5
4 9
6 2
7 8
6 10

 

출력 예시

 

57

 

 

---

 

풀이

 

1. 우선 한 명의 친구를 울렸을 때 몇 명의 친구의 사탕을 동시에 뺏을 수 있는지 알아내야 한다. 고전적 경로 탐색 방법을 이용해도 되고, 혹은 유니온-파인드 방법을 참조해도 된다.

 

2. 1의 과정 후에는 (총 울게 되는 친구의 수, 총 사탕 수)로 이루어진 정보 리스트가 남는다. 이 정보 리스트를 토대로 K 이내의 아이들을 울리며 최대 사탕 수를 구해야 한다. 따라서 가방 문제의 변종이라고 볼 수 있다. DP를 활용해 보자.

 

 

풀이 코드

from collections import deque, defaultdict
import sys
input = sys.stdin.readline

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

candy_list = list(map(int, input().split()))
friend_dict = defaultdict(list)
visited = [False]*N
total_candy = list()

for _ in range(M) :
  a, b = map(int, input().split())
  friend_dict[a-1].append(b-1)
  friend_dict[b-1].append(a-1)

for i in range(N) :
  if not visited[i] :
    people, candy = 1, candy_list[i]
    visited[i] = True
    q = deque([i])

    while q :
      now = q.popleft()
      for nxt in friend_dict[now] :
        if not visited[nxt] :
          visited[nxt] = True
          people += 1
          candy += candy_list[nxt]
          q.append(nxt)
    
    total_candy.append((people, candy))

dp = [[-1]*K for _ in range(len(total_candy)+1)]
dp[0][0] = 0

for i in range(len(total_candy)) :
  dp[i][0] = 0
  people, candy = total_candy[i]
  for j in range(K) :
    if dp[i][j] > -1 :
      dp[i+1][j] = max(dp[i+1][j], dp[i][j])
      if j + people < K :
        dp[i+1][j+people] = max(dp[i+1][j+people], dp[i][j] + candy)

print(max(dp[-1]))

풀이 완료!