[백준] No.1693 - 트리 색칠하기 (C++)

문제

 

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

1693번: 트리 색칠하기

 

 

풀이

 

solved.ac 난이도: Platium 3

 

상당히 해결하기 어려웠던 트리에서의 다이나믹 프로그래밍 문제.

해당 문제의 풀이는 koosaga님과 BaaaaaaaarkingDog님의 풀이를 참고하였습니다.

 

T(N): 반드시 N개의 색을 사용해야 트리를 최소 비용으로 칠할 수 있는 트리들 중에서 최소 노드 개수 라고하자.

 

반드시 N개의 색을 써야 한다면 루트 노드의 자식 노드들이 모두 1~N-1의 색으로 칠해져 있어 어쩔 수 없이 루트를 N으로 칠하는 경우이다. 

 

이러한 경우, 자식 노드들의 서브 트리도 루트를 해당 수(i)로 칠해야만 하는 트리를 구성하기 때문에

최소 노드 개수 T(N)은 아래와 같이 재귀적으로 표현할 수 있다.

 

T(1) = 1

T(2) = T(1) + 1 = 2

T(3) = T(2) + T(1) + 1 =  ( T(1) + 1 ) + 2 = 4

T(4) = T(3) + T(2) + T(1) + 1 = ( T(2) + T(1) + 1 ) + ( T(1) + 1 ) +  T(1) + 1 = 4 + 2 + 1 + 1 = 8

...

T(N) = T(N-1) + T(N-2) + ... + T(2) + T(1) + 1

= 2^(N-2) + 2^(N-3) + ... + 2^(1) + 2^0 =

2^(N-1)

이때 뒤에 붙는 + 1은 자기 자신(루트 노드)을 N번 색으로 칠하는 것을 의미한다.

 

T(N)의 의미를 조금 더 자세히 생각해보자.

위의 식에 따르면 T(3) =  4이다. 이때의 트리는 아래와 같다.

 

3개의 색으로 칠할 수 있는 최소 노드의 개수는 4개임을 의미한다.

 

물론 4개의 노드는 아래와 같이 더 작은 비용으로 칠할 수도 있다.

즉, T(N)은 최소의 비용만을 선택함에도 N의 색을 모두 사용해야 하는 최악의 경우이다.

 

여기서 우리가 T(N) (반드시 N개의 색을 사용해야 트리를 최소 비용으로 칠할 수 있는 트리들 중에서 최소 노드 개수)

을 찾는 이유는 노드의 수가 최대 100,000의 값을 가지기 때문이다.

만약 이를 그대로 dp로 구현한다면 100,000(각각의 노드를) X 100,000(1번 색에서 ~ 모든 색으로 모두 칠해보는 경우) = 10,000,000,000의 터무니없이 큰 경우의 수에서 최소 비용을 찾아보아야 한다.

하지만 T(N)을 알고 있다면 100,000개의 노드를 가능한 최소 비용의 색만을 선택할 때 적어도 몇 개의 색이 필요한지 알 수 있다.

 

T(N) = 2^(N-1) 이기 때문에 T(18) = 2^(17) = 131,072이다.

따라서 100,000개의 노드는 18개의 색으로도 모든 경우의 최소 비용 트리 구해낼 수 있다.

 

이후에는 DFS형식으로 최소 비용을 구하는 코드를 작성해 주면 된다.

 

코드

	#include <iostream>
	#include<vector>
	#include<string.h>
	using namespace std;
	int node_num;
	const int max_color = 19;
	int dp[100001][max_color];
	class Node; // 클래스 선언부
	vector<Node> tree;
	class Node{ //클래스 정의부
	public:
	int parent;
	vector<int> children;
	void FindParentDFS(int par, int now){
	parent = par;
	for(int i=0; i<children.size() ; ++i)
	if(children[i] != parent)
	tree[children[i]].FindParentDFS(now,children[i]);
	}
	int FindMinCost(int node, int now_color){
	int& ret = dp[node][now_color];
	if(ret != -1)
	return ret;
	int min_result=0;
	ret = now_color; //자신은 now_color로 칠해지므로 미리 cost를 추가
	for(int i=0; i<children.size() ; ++i){
	if(children[i] != parent){
	min_result = 1000000;
	for(int color=1; color<=max_color ; ++color){
	if(color != now_color){
	min_result = min(min_result, tree[children[i]].FindMinCost(children[i], color) );
	}
	}
	ret += min_result;
	}
	}
	return ret;
	}
	};
	int main(){
	ios_base::sync_with_stdio(0);
	cin>>node_num;
	tree = vector<Node>(node_num+1);
	int u,v;
	tree[0].children.push_back(1); //계산의 편의를 위해 1의 부모 노드인 0노드를 추가
	tree[1].children.push_back(0);
	for(int i=0; i<node_num-1 ; ++i){
	cin>>u>>v;
	tree[u].children.push_back(v);
	tree[v].children.push_back(u);
	}
	tree[0].FindParentDFS(0, 0); //0을 루트로 한 트리에서 각 노드의 부모를 찾아줌
	memset(dp, -1, sizeof(dp));
	cout<<tree[0].FindMinCost(0, 0)<<'\n';
	return 0;
	}

view raw [BaekJoon]_1693_트리 색칠하기.cpp hosted with ❤ by GitHub