Tree DP란?
흔히 트리DP라고 불리는 테크닉이 있습니다. 말 그대로 트리에서 DP를 하는 것입니다.
DP는 기본적으로 부분 문제의 해를 이용해 큰 문제의 해를 구하는 기법입니다. 트리에서도 이 개념을 적용할 수 있습니다.
트리에서의 DP는 서브 트리에서 구한 해를 이용해 전체 트리의 해를 구하는 방식으로 진행이 됩니다. dp[i] = i를 루트로 하는 서브 트리의 ~~~ 와 같은 식으로 DP Table을 정의합니다.
dp는 보통 선형으로 이루어진 공간에서 이루어졌지만, 트리는 비선형 구조입니다. 트리에서 dp를 하기 전에, 탐색 순서를 미리 정해주는 것이 일반적입니다.
탐색 순서를 정하는 것은 dfs를 돌면서 나오는 트리, 즉 dfs tree를 기준으로 합니다.
트리DP도 대부분 상태DP가 들어갑니다. 대략 dp[i][j] = i를 루트로 하는 서브트리에서 i의 상태가 j일 때 ~~~ 와 같은 식으로 합니다.
문제 풀이
백준2213 트리의 독립집합(링크) 문제를 봅시다. 최대 독립 집합을 구하는 문제입니다.
각 정점은 포함되거나 포함 되지 않는, 두 가지 상태 중 한 가지에 속하게 됩니다. 그러므로 dp배열을 아래와 같이 정의합시다.
dp[i][0] = i를 루트로 하는 서브트리에서 i를 포함하지 않을 때의 정답
dp[i][1] = i를 루트로 하는 서브트리에서 i를 포함할 때의 정답
백준1693 트리 색칠하기(링크) 문제를 봅시다. 트리에 있는 각각의 정점은 어떤 색깔로 칠해질 수 있습니다. dp배열을 아래와 같이 정의합시다.
dp[i][j] = i를 루트로 하는 서브트리에서 i를 j로 칠할 때의 정답
이런 식으로 문제를 해결할 수 있습니다. 두 문제에 대한 자세한 풀이는 (여기, 여기)에 있습니다.
추천 문제
- http://icpc.me/2213 위에서 설명한 문제입니다.
- http://icpc.me/1693 위에서 설명한 문제입니다.
- http://icpc.me/2533 풀이