Baekjoon(백준) 25091번 - Chain Reactions (Google Codejam 2022 qualification problem D)

백준 25091번.
문제 제목 : Chain Reactions
백준 25091

2022 구글 코드잼의 qualification round 에서 D 번 문제로 나왔다. (A, B 번은 너무 쉬워서 패스)

문제 해석

간단하게 설명하기가 어렵다. 문제 원문 그대로를 이해하는 것이 최선이다…

풀이 전략

greedy 와 tree 를 사용하고 약간의 memoization을 사용하면 $O(N)$ 에 해결할 수 있다.
문제에서 abyss (?) 를 pointing 하는 노드를 tree 의 root라 생각하면 chain reaction 이라고 하는 것을 하나의 tree 로 생각할 수 있다. 여기서 주의해야 할 것이 abyss를 pointing 하는 노드가 여러개 있으면 tree 가 각각 여러개 있는 것으로 생각해야 한다.
각 노드마다 그 노드의 숫자, child를 기록하고 여기에 추가로 2가지를 더 기록한다.

maxn : 그 노드가 포함된 path (문제를 읽어보면 중간에 두개 이상의 노드가 한 parent를 pointing 하면 ‘reaction’은 겹쳐질 수 없고 한 child만 parent 로 ‘reaction’ 이 이어지고 나머지 child는 ‘reaction’ 이 끊기며 그 때 해당 노드가 속한 ‘reaction’ 에서 가장 큰 수가 ‘fun’ 수치에 더해진다고 되어 있다. path 라 함은 그 노드가 속한 ‘reaction’이 거치는 node 들 이라 생각하면 된다) 위에 있는 노드들의 숫자 중 최대값

fun : 그 노드를 root로 하는 subtree의 ‘fun’ 수치. 즉, 문제에서 구하고 싶은 것은 abyss 를 pointing 하는 노드들 fun 수치들의 합이다.

이 2가지를 각 node 마다 memoization 하는 것이다.
만약 지금 노드의 child 가 하나밖에 없으면 maxn은 지금 노드의 숫자와 child의 maxn중 최대값, fun은 child의 fun 값을 그대로 가져오면 된다.
하지만, 만약 지금 노드의 child 가 두 개 이상이면 생각을 해야 한다. 이 때 child 들 중 maxn 값이 큰 쪽을 현재 노드와 path로 계속 이어가고 작은 쪽을 끊어내어 fun 수치 값에 더하면 어떻게 되겠는가? 작은 값이 더해지고 큰 값을 버리는 꼴이므로 ‘fun’ 수치는 작아질 것이다. (즉, 문제에서는 ‘fun’ 수치의 최대값을 구해야 하므로 맞지 않다) 따라서, child 들 중 maxn 값이 작은 쪽을 현재 노드와 reaction path 로 계속 이어주고 나머지 child는 거기서 끊고 각각의 fun 수치 값을 답에 더해주어야 한다. (greedy 기법)
또한, maxn은 이어진 child의 maxn과 현재 노드의 숫자 중 최대값이 될 것이고, fun 은 모든 child의 fun값과 maxn을 더한 후 이어진 child의 maxn 만 빼주면 된다.

구현

tree를 형성하고 DFS 탐색을 해주면 된다. DFS 재귀탐색으로 말단 node 까지 내려간 다음 올라오면서 앞에서 설명한 알고리즘을 적용한다. 그러면 현재 노드의 memoization 에 child 의 값들이 반영되며 이것이 반복되면 root node 의 fun 값이 곧 그 tree의 fun 값이 된다. 몇 개 변수 (fun과 관련된 변수) 들은 integer 범위를 넘길 수 있다. 이에 주의하면 된다.
자세한 solution code 는 github 참고

baekjoon 25091 solution code