2533 - Java

문제

트리에서의 다이나믹 프로그래밍

• 트리에서의 다이나믹 프로그래밍은 보통 i번째 노드를 루트로 하는 서브트리에서 i번째 루트노드를 포함했을때와 포함 안했을때 중 최적값을 계산하는 방식이다.

• DFS를 사용하여 leaf node의 값부터 알아내면서 문제를 해결하는 방식

기본적인 뼈대는 아래와 같다

visit배열을 하나 만들고, 루트 노드로부터 자식 노드를 순차방문하면서 방문했으면 무시하고 방문을 안했을 때 dfs 재귀로 들어간다. 그렇게 leaf node부터 값을 구하여 이를 이용해 root node의 값을 구해간다.

풀이

package com;

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

public class Main {
	
	static int n;
	static boolean[] visit;
	static LinkedList<Integer>[] tree;
	static int[][] dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp = new int[n+1][2]; //0이면 얼리x, 1이면 얼리
		visit = new boolean[n+1];
		tree = new LinkedList[n+1];
		for (int i = 1; i < n+1; i++) {
			tree[i] = new LinkedList<>();
		}
		
		for (int i = 0; i < n-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			tree[u].add(v);
			tree[v].add(u);
		}
		int root = 1;
		dfs(root);
		System.out.println(Math.min(dp[root][0], dp[root][1]));
	}

	private static void dfs(int root) {
		visit[root] = true;
		dp[root][0] = 0;
		dp[root][1] = 1;
		
		LinkedList<Integer> item = tree[root];
		for(int child : item) {
			if(!visit[child]) {
				dfs(child);
				dp[root][0] += dp[child][1];
				dp[root][1] += Math.min(dp[child][0], dp[child][1]);
			}
		}
	}

}

• dp를 2차원 배열로 선언
• 0이면 얼리가 아닌 경우이고, 1이면 얼리인 경우
• 부모가 얼리라면, 자식은 얼리일수도 있고 아닐수도 있다.
  • dp[부모][1] += for(자식) min(dp[자식][0], dp[자식][1])
• 부모가 얼리가 아니라면, 자식은 무조건 얼리가 되어야 한다.
  • dp[부모][0] += for(자식) dp[자식][1]

아직 트리에서의 DP는 감이 별로 안잡히니 여러 문제를 풀어봐야 할듯
코테에서도 비슷한 문제를 본적이 있다. 그때 문제랑 비슷했던 문제
https://www.acmicpc.net/problem/7812