[코드 트리 조별 과제] Tree DP 공부하기

DP를 적용하기 가장 좋은 예시 : Rooted Tree 문제

Rooted Tree이기 때문에 항상 부모 자식 관계가 존재합니다. 자식 노드의 결과를 활용해 부모 노드의 결과를 유추할 수 있습니다. dfs로 리프노드까지 도달 후 올라오면서 자식의 결과로 dp 배열을 채워나갑니다.

시간 복잡도

Rooted Tree 문제를 DP로 풀 경우 대부분 DFS로 한번에 해결합니다. DFS의 시간 복잡도인 O(V+E)만에 문제를 해결할 수 있습니다.

예시

트리와 쿼리

정점을 루트로 하는 서브트리에 속한 정점의 수를 출력하는 문제입니다.

가짜 문제를 정의합니다.

D[i] = i를 루트로 하는 subtree의 정점 개수 

초기값을 정의합니다.

리프노드는 자식을 가지고 있지 않아, 해당 노드만 1로 초기화합니다.

점화식을 구합니다.

D[부모노드] = sum(d[자식노드들])+1(자기자신)

d 배열을 채워나가는 dfs는 다음과 같습니다.

private static void dfs(int current, int parent){  
	//어떤 노드건 자기 자신도 무조건 서브 트리에 속합니다. 
	//최소한 개수가 1은 보장됩니다. 
    d[current] = 1;  
  
    for(int child : graph[current]){  
        if(child==parent) continue;  
  
        dfs(child, current);  
        d[current]+=d[child];  
    }  
}

예제

코드 트리 : 인접한 노드

https://www.codetree.ai/missions/9/problems/adjacent-node-2?&utm_source=clipboard&utm_medium=text

문제는 위 링크와 같습니다.

흔한 노드를 선택하는 경우의 수로 dp 분기처리가 나뉩니다. 이 경우 골라야할 노드도 dfs를 한번더 실행하는 것만으로 구할 수 있으니 잘 기억해 둡시다.

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens; 
    
    static int[] nodes; 
    static int[][] d;
    static List<Integer>[] graph; 
    static List<Integer> route;
    static final int YES =1;
    static final int NO = 0; 

    public static void main(String[] args) throws IOException{
        int n = Integer.parseInt(buffer.readLine());
        nodes = new int[n+1];
        d = new int[n+1][2];
        graph = new List[n+1]; 
        route = new ArrayList<>(); 

        tokens = new StringTokenizer(buffer.readLine());
        for(int node=1; node<=n; node++){
            graph[node] = new ArrayList<>();

            nodes[node] = Integer.parseInt(tokens.nextToken()); 
        }

        for(int edge=0; edge<n-1; edge++){
            tokens = new StringTokenizer(buffer.readLine());
            int node1 = Integer.parseInt(tokens.nextToken());
            int node2 = Integer.parseInt(tokens.nextToken()); 

            graph[node1].add(node2);
            graph[node2].add(node1);
        }


        dfs(1, -1);

        if(d[1][YES]>d[1][NO]){
            
            findRoute(1,YES, -1);
        }else{
            findRoute(1, NO, -1);
        }

        StringBuilder result = new StringBuilder(); 
        result.append(Math.max(d[1][YES], d[1][NO])).append("\n");
        Collections.sort(route);

        for(int node : route){
            result.append(node).append(" ");
        }
        System.out.println(result);
        

        
    }

    private static void findRoute(int current, int status, int parent){
        
        if(status==YES){
            route.add(current);

            for(int child : graph[current]){
                if(child == parent) continue; 
                findRoute(child, NO, current);
            }
        }else{
            for(int child : graph[current]){
                if(child == parent )continue; 
                if(d[child][YES]>d[child][NO]){
                    findRoute(child, YES, current);
                }else{
                    findRoute(child, NO, current);
                }
            }
        }

    }

    private static void dfs(int current, int parent){
        d[current][YES] = nodes[current];

        for(int child : graph[current]){
            if(child == parent) continue; 

            dfs(child, current); 

            d[current][YES] += d[child][NO];
            d[current][NO] += Math.max(d[child][NO], d[child][YES]);
        }

    }
}