접근
트리의 순회와 동적 계획법으로 풀어내야하는 문제이다. 동적계획법으로 풀어내야 할 것까지는 알 것 같은데, 어떤 정보를 저장해나가야 할 지 감이 안왔어서 그 부분을 찾아봤다.
DP[num] = {num가 팀장인 팀에서 팀장이 불참일 때 최적해, num가 팀장인 팀에서 팀장이 참여일 때 최적해}
이와 같이 DP를 정의하니 문제를 푸는 방법을 알 수 있었다.
트리를 후위 순회하면서 노드를 처리할 때, DP를 업데이트 한다.
- 노드가 불참인 경우 : 자식들 중 적어도 하나는 참여해야 한다.
- 노드가 참여인 경우 : 모든 자식들의 불참, 참여 최적해 중 최솟값을 더한다.
2번 케이스의 경우는 반복문을 돌면서 불참, 참여 중 더 작은 것을 더하면 된다.
// root가 참여하는 경우 -> child는 아무도 참여하지 않을 수도 있다.
int parent = parents[root];
int minDiff = Integer.MAX_VALUE;
int minChild = 0;
for(int incident : incidents[root]){
if(incident != parent){
DP[root][1] += Math.min(DP[incident][0],DP[incident][1]);
if(minDiff > DP[incident][1] - DP[incident][0]){
minDiff = DP[incident][1] - DP[incident][0];
minChild = incident;
}
}
}1번 케이스의 경우 자식들이 불참하는 해만 DP[root][0]에 더해지면 안된다. 적어도 하나의 자식은 참여를 해야하고 그 결과가 모두 불참하는 것보다 바로 다음으로 큰 값이여야 한다.
자식의 참여-불참이 최소인 녀석은 무조건 참여시키면 앞의 조건을 만족시킬 수 있다.
// root가 불참하는 경우 -> child 중 적어도 하나는 참여해야함(참여-불참 이 가장 작은 놈으로)
for(int incident : incidents[root]){
if(incident != parent){
if(incident == minChild){
DP[root][0] += DP[incident][1];
}else{
DP[root][0] += Math.min(DP[incident][0],DP[incident][1]);
}
}
}DFS
후위순회 dfs를 하면 된다. 근데 문제 조건이 상당히 빡빡하다.
sales 배열의 크기는 2 이상 300,000 이하입니다.
레벨 4에 들어서 재귀로 dfs를 구현하니 거의 99프로 스택오버플로우가 나서 반복문으로 풀기로 했다.
그런데 전위순회를 반복문으로 푸는 건 간단했는데, 중위 혹은 후위순회는 반복문으로 푼 적이 없다.
여태까지 함수의 콜스택에 의존해서 대부분 재귀로만 풀었더니 반복문으로 후위순회를 구현해본 적이 없어서 chatGPT에게 물어봤었다.
public static List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Object> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Object obj = stack.pop();
if (obj instanceof TreeNode) {
TreeNode node = (TreeNode) obj;
stack.push(node.value);
stack.push(node.right);
stack.push(node.left);
} else if (obj instanceof Integer) {
result.add((Integer) obj);
}
}
return result;
}후위순회로 리스트에 트리의 원소값(정수)를 넣는 과정이다.
스택에 들어가는 원소가 TreeNode 와 Integer이고 TreeNode를 팝한 경우에는 다음에 방문해야할 노드를 넣는다.
정수를 팝한 경우에는 노드의 값을 처리한다.
즉, 방문과 처리를 스택에 분리하여 넣는 것이다.
나는 이 방법을 문제에 이렇게 적용해봤다.
- 방문을 스택에 넣을 때 : -노드값을 넣는다.
- 처리를 스택에 넣을 때 : 노드값을 넣는다.
import java.util.*;
class Solution {
int[] sales;
Set<Integer>[] incidents;
int[] parents;
int[][] DP;
int[] sub;
public int solution(int[] sales, int[][] links) {
this.sales = sales;
DP = new int[sales.length + 1][2];
sub = new int[sales.length + 1];
Arrays.fill(sub, Integer.MAX_VALUE);
incidents = new Set[sales.length + 1];
parents = new int[sales.length + 1];
for(int i = 0;i<incidents.length;i++){
incidents[i] = new HashSet();
}
for(int[] link:links){
int src = link[0];
int dest = link[1];
incidents[src].add(dest);
incidents[dest].add(src);
}
for(int i=0;i<sales.length;i++){
DP[i+1][1] = sales[i];
}
bfs();
dfs();
return Math.min(DP[1][0], DP[1][1]);
}
void dfs(){
Stack<Integer> stk = new Stack();
stk.push(-1);
while(!stk.isEmpty()){
int root = stk.pop();
if(root > 0){
// root가 참여하는 경우 -> child는 아무도 참여하지 않을 수도 있다.
int parent = parents[root];
int minDiff = Integer.MAX_VALUE;
int minChild = 0;
for(int incident : incidents[root]){
if(incident != parent){
DP[root][1] += Math.min(DP[incident][0],DP[incident][1]);
if(minDiff > DP[incident][1] - DP[incident][0]){
minDiff = DP[incident][1] - DP[incident][0];
minChild = incident;
}
}
}
// root가 불참하는 경우 -> child 중 적어도 하나는 참여해야함(참여-불참 이 가장 작은 놈으로)
for(int incident : incidents[root]){
if(incident != parent){
if(incident == minChild){
DP[root][0] += DP[incident][1];
}else{
DP[root][0] += Math.min(DP[incident][0],DP[incident][1]);
}
}
}
// System.out.printf("%d가 불참일 때 최적 : %d%n", root, DP[root][0]);
// System.out.printf("%d가 참일 때 최적 : %d%n", root, DP[root][1]);
}else {
/**
방문
*/
stk.push(-root);
int parent = parents[-root];
for(int incident : incidents[-root]){
if(incident != parent){
stk.push(-incident);
}
}
}
}
}
void bfs(){
Queue<Integer> Q = new LinkedList();
Q.add(1);
while(!Q.isEmpty()){
int qLen = Q.size();
for(int i=0;i<qLen;i++){
int num = Q.poll();
int parent = parents[num];
for(int child:incidents[num]){
if(child != parent){
parents[child] = num;
Q.add(child);
}
}
}
}
}
}