[BOJ]20303. 할로윈의 양아치 (python)

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

20303번: 할로윈의 양아치

 

문제

Trick or Treat!!

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

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

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

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

입력

첫째 줄에 정수 N$N$, M$M$, K$K$가 주어진다. N$N$은 거리에 있는 아이들의 수, M$M$은 아이들의 친구 관계 수, K$K$는 울음소리가 공명하기 위한 최소 아이의 수이다. (1≤N≤30 000$1 \leq N \leq 30\ 000$, 0≤M≤100 000$0 \leq M \leq 100\ 000$, 1≤K≤min{N,3 000}$1 \leq K \leq \min\left\{N, 3\ 000\right\}$)

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 c1,c2,⋯,cN$c_1, c_2, \cdots, c_N$이 주어진다. (1≤ci≤10 000$1 \leq c_i \leq 10\ 000$)

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

출력

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

 

 

풀이

https://ggam-nyang.tistory.com/39

[BOJ]12865. 평범한 배낭 (python)

양아치 문제이다

이 문제와 핵심 코드는 거의 똑같다.
전형적인 배낭 문제다!
응용이 된 부분은, 그래프 탐색을 이용하여 연결된 친구들을 구해줘야한다.
즉, 위 문제와 같이 (물건의 무게, 물건의 가치)가 주어지지 않기 때문에, 연결된 친구들을 탐색하여
(연결된 친구들, 그 친구들의 candy 총합)을 만들어 준 후, 배낭 문제와 동일한 로직을 사용하면 된다!!!

 

코드

import sys
import collections
read = sys.stdin.readline


# 입력값 받기
children_N, relationship_N, resonance = map(int, read().strip().split())

candy_list = [0] + list(map(int, read().strip().split()))
friend_list = [[] for _ in range(children_N + 1)]
for _ in range(relationship_N):
    a, b = map(int, read().strip().split())
    friend_list[a].append(b)
    friend_list[b].append(a)

# 연결된 친구의 group을 구하기 위한 함수
visited = [0] * (children_N + 1)
def bfs(x):
    group = [[x], candy_list[x]]
    queue = collections.deque()
    queue.append(x)
    visited[x] = 1

    while queue:
        now_x = queue.popleft()

        for i in range(len(friend_list[now_x])):
            if visited[friend_list[now_x][i]] == 0:
                friend = friend_list[now_x][i]
                visited[friend] = 1
                queue.append(friend)
                group[0].append(friend)
                group[1] += candy_list[friend]

    return group


# 연결된 친구들의 그룹을 표시함. [[연결된 친구 번호들], 총 candy 수] 로 표현함
children_group = []
for i in range(1, children_N + 1):
    if visited[i] == 0:
        children_group.append(bfs(i))
children_group = [0] + children_group

dp = [[0] * (resonance + 1) for _ in range(len(children_group))]

# 배낭 문제와 동일한 로직으로 해결!!
for i in range(1, len(children_group)):
    children, candy = len(children_group[i][0]), children_group[i][1]
    for reso in range(1, resonance + 1):
        if reso <= children:
            dp[i][reso] = dp[i - 1][reso]
        else:
            dp[i][reso] = max(dp[i - 1][reso - children] + children_group[i][1], dp[i - 1][reso])

print(dp[len(children_group) - 1][resonance])