Tree DP

그래프dp에 익숙하지 않은 사람들을 위해 자세히 쓰려고 한다. 이미 이 유형에 어느정도 익숙해졌다면 문제 위주로 따라와주면 될 것 같다.

마지막 문제에선 트리의 구조(루트)를 바꾸면서 백트래킹하여 정답을 갱신해나가는 rerooting에 대해서도 알아보겠다.

학습 시간은 최대로 잡아서 1번 문제 한시간, 2번 문제 한시간반, 3번 문제 두시간반 정도 보면 될 것 같다.

참조투명성에 대한 개념이 기억이 안난다면.. (대충 수학에서 다루는 함수생각하면 됨)

https://ko.wikipedia.org/wiki/%EC%B0%B8%EC%A1%B0_%ED%88%AC%EB%AA%85%EC%84%B1

<개요>

그래프에선 어떤 정점 u에 대한 상태가 인접한 정점 v에 대한 상태로 정의되며 참조 투명하다면 dp를 적용할 수 있다.

좀 더 쉬운 말로, 정점u에 대한 상태가 인접 정점 v의 상태를 사용해서 점화식이 세워진다면, dp를 적용할 수 있다.

트리에선 좀 특수하게, 정점 u의 상태가 인접 정점 v의 상태나 루트의 상태로 정의 된다면 dp를 적용할 수 있다.

정점 u를 루트로 하는 서브트리에 대한 상태를 묻는 문제가 자주 나온다.

쉬운 예로, 트리에서 정점 u의 깊이를 $depth[u]$라고 한다면 $depth[u] = depth[ parent(u) ]+1$이다.

u에 대한 깊이가 인접한 정점 v에 대한 깊이로 정의(점화식)되므로 dp를 사용할 수 있는 것이다.

(트리의 깊이를 갱신하는 코드)

int depth[MAX]; 
void makeTreeDepth(int u, int parent){
	depth[u] = depth[parent]+1;
    
    for(int v : adj[u]) if(v!=parent) 
    	makeTreeDepth(v,u);
}

참고로 위와 같이 dfs 파라미터에 parent를 의미하는 이전 정점을 같이 보내준다면, 보통의 경우 child, parent배열을 나눌 필요 없이 인접리스트만으로 문제를 풀 수 있다.

<1번 문제> - usaco gold

https://www.acmicpc.net/problem/15458

트리dp 유형에서 쉽게나오면 이정도 수준으로 나오는 것 같다. 문제설명을 먼저 읽고 영어지문을 읽으면 더 이해 잘 될것.

(문제설명)

최대 $10^5$개의 헛간 n개가 주어진다. 헛간은 서로 연결되어 트리를 이룬다.

헛간을 세 가지 색을 이용하여 색을 칠하려고 하는데, 인접한 두 헛간의 색은 항상 다르게 칠하려고 한다.

k개의 헛간은 이미 색칠 돼 있다.

헛간 그래프와 이미 색칠된 헛간과 그 색이 주어질 때, 모든 헛간을 색칠하는 경우의 수를 구하라.

(너무 클 수 있으므로 $10^9+7$로 모듈러한 값을 구해라)

(풀이보기 전)

잘 안된다면 점화식까지만 세워보자. (~30분)

(풀이)

트리이지만 따로 루트는 정해주지 않았다. 모든 경우에 등장하는 1번 헛간을 루트로 생각하자.

부모 정점에서의 색에 따라서 현재 색칠할 수 있는 색이 정해진다. 따라서 u번 정점을 루트로 하는 서브트리를 색칠하는 경우의 수를 $dp[u]$라 하고 문제를 풀려고 한다면 정보가 부족하다.

부모노드에서 칠한 색을 pc라고 할 때 u번 정점을 루트로 하는 서브트리를 칠하는 경우의 수를 $dp[u][pc]$라고 하자.

u번 정점이 색이 칠해지지 않은 상태일 때와 색이 칠해진 상태일 때로 나누어서 생각해보면 된다.

1) 색이 칠해지지 않은 경우

pc와 다른 색상 c1, c2에 대해

$\prod_{v \in adj(u)} dp[v][c1]$ 이거랑

$\prod_{v \in adj(u)} dp[v][c2]$ 이거 더해주면 된다.

2) 색이 이미 칠해진 경우.

pc와 색상이 같다면 불가능하므로 0을 반환.

pc와 색상이 다르다면 $\prod_{v \in adj(u)} dp[v][colorof[u]]$

일반 dp를 풀때와 같이 메모이제이션도 잊지않아야 한다.

트리면 O(n)에 다 돌아보니 메모이제이션이 의미가 없지 않냐??

-> 문제에서 준 구조는 트리가 맞지만, 풀이과정을 잘 생각해보면 정점마다 색이 칠해지지 않은 경우 두가지 색 중 하나를 선택하므로 최악의경우 2^n시간이 걸린다. 따라서 메모이제이션을 해줘야한다.

(코드)

ll n, k, dp[MAX][4], clr[MAX]; //색은 1~3사용.
vector<int> adj[MAX];

ll f(int u, int pc, int p) {
	//메모이제이션
	ll& ret = dp[u][pc];
	if (ret != -1) return ret;

	//색이 칠해져 있지 않은 경우
	if (clr[u] == 0) {
		ret = 0;
		//가능한 색상을 적용한 경우를 다 더해준다.
		for (int c = 1; c <= 3; c++) {
			if (c == pc) continue;
			ll temp = 1;
			//모든 인접한 정점에 대해선 곱해준다.
			for (int v : adj[u]) {
				if (v == p) continue;
				temp *= f(v, c, u);
				temp %= MOD;
			}
			ret += temp;
			ret %= MOD;
		}
	}
	// 이미 색이 칠해진 경우
	else { 
		//이전 색과 모순되는 경우
		if (pc == clr[u]) 
			return ret = 0;

		//모든 인접한 정점에 대해서 곱해준다.
		ret = 1;
		for (int v : adj[u]) {
			if (v == p) continue;
			ret *= f(v, clr[u], u);
			ret %= MOD;
		}
	}
	return ret;
}

int main() {
	FAST;
	cin >> n >> k;
	for (int i = 0, u, v; i < n - 1; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 0, u, c; i < k; i++) {
		cin >> u >> c;
		clr[u] = c;
	}

	memset(dp, -1, sizeof(dp));
	//pc==0으로 넘기면 식의 통일성 유지 가능
	cout << f(1, 0, 0) << '\n';
}

<2번문제> - usaco gold

https://www.acmicpc.net/problem/15746

여기서부터 조금 어려워짐.

(문제설명)

최대 $10^5$개의 정점이 n개 주어진다. 이 정점은 트리 구조를 이룬다. 리프노드는 파일이고 그 외는 폴더이다.

정점들은 1~n까지의 번호로 표현되고 이름이 주어진다. 루트는 항상 1로 고정이다.

현재 폴더가 folder2일 때 각 파일로의 경로는 다음과 같이 나타낸다.

../file1

file2

../../folder3/file3

../../file4

이 때 모든경로의 길이는 모든 character의 개수를 센 것으로 위의 경우 43 이다.

각 파일명, 인접한 정점번호가 주어질 때 모든경로의 길이의 최소값을 구해라.

(시작점이 folder1, folder2, bessie, folder3일때를 생각해주면 된다.)

(풀이보기 전)

직접 그림을 그려보고 경로도 조금 써가면서 풀기를 바람. 개인적으로 1시간 이상 고민해볼 가치가 있는 문제라고 생각됨.

u를 루트로 하는 서브트리의 리프노드(파일) 개수와 전체 트리에서 1을 루트로 할때 경로의 길이를 전처리 해둬야 한다.

점화식을 세울 때 1번정점(전체 루트)의 정보를 필요로 한다.

(풀이)

먼저 간선 가중치를 생각해보자.

자식 -> 부모인 경우 3 (../)

부모 -> 자식인 경우 length(폴더명)+1 또는 length(파일명)

u를 루트로하는 서브트리의 리프노드 개수 $leaf[u]$와 전체 트리의 루트 1에서 시작점으로 하는 경로 길이의 합 $dp[1]$을 전처리 해두자. -> O(n)

int numOfLeaf(int u) {
	int& ret = leaf[u];
	if (ret != -1) return ret;

	ret = isLeaf[u];
	for (int v : adj[u])
		ret += numOfLeaf(v);
	return ret;
}

void makeDp_1(int u) {
	for (int v : adj[u]) {
		if (isLeaf[v]) 
        		dp[1] += s[v].size();
		else 
        		dp[1] += leaf[v] * (s[v].size() + 1);

		makeDp_1(v);
	}
}

numOfLeaf도 dp임

간선가중치를 고려해서 dp[1]초기화

예시에서 1(bessie)과 인접한 점 2(folder1)에 대한 상태를 1에 대한 상태로 갱신해 줄 수 있다.

1부터 시작하는 경로와 2부터 시작하는 경로를 잘 살펴보면...

dp[1]에서 dp[2]로의 변화를 leaf와 폴더,파일명의 길이로만 알 수 있다.

다시말해서, dp[parent], leaf[root], leaf[child]의 정보만으로 상수시간에 알 수 있다.

부모->자식으로 이동하며 dp를 갱신한다면 자식서브트리의 리프노드 개수만큼의 경로는 길이가 줄어든다.

leaf(child) 개의 경로가 (len(s[child])+1) 만큼 줄어드는 것! (손으로 써보면 바로 알 수 있다.)

그 외 나머지 경로는 모두 ../이 앞에 붙는다.

leaf(root)-leaf(child) 개의 경로가 3만큼 늘어난다.

void dfs(int u) {
	ans = min(ans, dp[u]);
	for (int v : adj[u]) {
		if (isLeaf[v]) continue;
		dp[v] = dp[u] + 3 * (leaf[1] - leaf[v]) - (s[v].size() + 1) * leaf[v];
		dfs(v);
	}
}

위 코드와 같이 dp와 정답을 갱신해주면 된다.

(이처럼 정석 탑다운 재귀 dp형태를 따르지 않고도 갱신할 수 있다.)

(코드)

int leaf[MAX], n;
string s[MAX];
vector<int> adj[MAX];
bool isLeaf[MAX];
ll ans = 2e18, dp[MAX];

int numOfLeaf(int u) {
	int& ret = leaf[u];
	if (ret != -1) return ret;

	ret = isLeaf[u];
	for (int v : adj[u])
		ret += numOfLeaf(v);
	return ret;
}

void makeDp_1(int u) {
	for (int v : adj[u]) {
		if (isLeaf[v]) dp[1] += s[v].size();
		else dp[1] += leaf[v] * (s[v].size() + 1);

		makeDp_1(v);
	}
}

void dfs(int u) {
	ans = min(ans, dp[u]);
	for (int v : adj[u]) {
		if (isLeaf[v]) continue;
		dp[v] = dp[u] + 3 * (leaf[1] - leaf[v]) - (s[v].size() + 1) * leaf[v];
		dfs(v);
	}
}

int main() {
	FAST;
	cin >> n;
	for (int i = 1, m; i <= n; i++) {
		cin >> s[i] >> m;
		if (m == 0) isLeaf[i] = true;
		for (int j = 0, v; j < m; j++) {
			cin >> v;
			adj[i].push_back(v);
		}
	}

	memset(leaf, -1, sizeof(leaf));
	numOfLeaf(1);
	makeDp_1(1);
	dfs(1);

	cout << ans << '\n';
}

<3번 문제> cf edu #67 E

https://codeforces.com/contest/1187/problem/E

사실 조금더 쉽게 풀 순 있다곤 하지만,https://codeforces.com/blog/entry/68111

문제 제작자 피셜로 rerooting 테크닉은 자주 쓰이니까 알아두라고 함.

필자 기준 에디토리얼 이해하는데 5시간은 쓴듯ㅜㅜ

(설명)

https://suuntree.tistory.com/144?category=816575

<생각>

트리dp는 인접한 두 정점 사이의 변화나 연관을 찾아내서 푸는 경우가 많다. 빡센 전처리와 같이 나오는 경우가 많아서 문제를 재정의하는 과정이 아주 필수적이다.

재귀가 주를 이루는 만큼 탄탄한 구현력이 바탕이 돼야 한다고 본다.

위 세 문제만 제대로 풀 줄 안다면 같은 유형이 나왔을 때 당황하지 않을 수 있을 것 같다.

+추가 문제

https://codeforces.com/contest/1324/problem/F(cf627(div3)-F)

BOJ/ 17831 대기업 승범이네

17831번: 대기업 승범이네

첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대로 공백으로 구분되어 주어진다. 세 번째 줄에 i번 판매원의 실력을 나타내는 정수 A1, A2, …, AN (0 ≤ Ai ≤ 100)이 순서대로 공백으로 구분되어 주어진다.

www.acmicpc.net

'algorithm' 카테고리의 다른 글

이중 연결 요소(BCC), 단절점, 단절선 (0)	2020.05.10
Euler Tour Tree(ETT) (0)	2020.03.29
knapsack (0)	2020.03.13

sunwooruz

Tree DP

'algorithm' 카테고리의 다른 글

티스토리툴바

Tree DP

'algorithm' 카테고리의 다른 글

'algorithm' Related Articles

티스토리툴바