12995번: 트리나라

12995번: 트리나라 - DP

kks227님 블로그의 동적 계획법 5를 읽고 인상 깊어 작성하게 되었다.

트리에서 DP를 사용하는 문제 유형에 대하여 설명하는데 그 중

노드 u를 루트로 하는 서브트리 안에서 모든 자식 노드에 분배를 해야하는 문제를 어떤 식으로 접근할까?에 대한 유형이다.

이 문제는 트리가 주어질 때 크기가 K인 트리를 만들기 위한 경우의 수를 묻는 문제이다.

이런 문제를 풀 때 기본적인 아이디어는 

u의 자식 노드를 v1, v2, ... vm이라 하면

u와 v1을 루트로 하는 서브트리랑만 연결 될 때,

u와 v1, v2를 루트로 하는 서브트리랑만 연결 될 때,

...

u와 v1, v2, ... vm을 루트로 하는 서브트리랑만 연결 될 때 순으로 구하게 된다.

약간 플로이드 와샬에서 i 정점에서 j 정점까지의 최단거리를

k 정점을 추가적으로 경유하였을 때의 값으로 갱신하여 구했던 것과 비슷한 느낌을 받았다.

dp식을 dp[u][m][k] = '노드 u를 루트로 하는 서브트리 안에서 v1, v2, ... vm을 루트로 하는 서브트리랑만 연결 될 때

노드 u를 포함하면서 k개의 노드로 이루어진 서브트리의 개수'라고 정의하자.

dfs를 이용하여 자신의 자식노드에 대한 값을 모두 계산한 뒤 u를 계산한다고 할 때,

v1을 루트로 하는 서브트리랑만 연결 될 때 k개를 만들기 위해서는 v1의 k-1개가 필요하므로

dp[u][1][k] = dp[v1][v1의 자식 개수][k-1] 가 된다.

이후 v1, v2, ... vi를 루트로 하는 서브트리랑만 연결 될 때 k개를 만들기 위해서는

dp[u][i-1][x] = u와 v1, v2, ... v(i-1)을 루트로 하는 서브트리에서 x개의 노드로 이루어진 서브트리의 개수

dp[vi][vi의 자식 개수][k-x] = vi를 루트로 하는 서브트리에서 k-x개의 노드로 이루어진 서브트리의 개수

이므로 x가 1부터 k보다 작을때까지

dp[u][i][k] += dp[u][i-1][x] * dp[vi][vi의 자식 개수][k]를 해주면 된다.

이 때 초기값 또한 필요한데

dp[i][노드 i의 자식 개수][0]는 노드 i를 루트로 하는 서브트리에서 0개의 노드로 이루어진 서브트리의 개수를 뜻하므로 1,

dp[i][노드 i의 자식 개수][1]는 노드 i를 루트로 하는 서브트리에서 1개의 노드로 이루어진 서브트리의 개수를 뜻하므로 1이다.

이와 같은 방법을 진행한 뒤 모든 i에 대하여

dp[i][노드 i의 자식 개수][K]의 값을 나머지 연산에 신경 써서 모두 더해주면 풀 수 있는 문제이다.