[백준/BOJ] 백준 1693번 : 트리 색칠하기

www.acmicpc.net/problem/1693

1693번: 트리 색칠하기

트리를 만들고 트리 DP(트리에서의 다이나믹 프로그래밍)를 이용해서 문제를 해결했는데, 100000(n의 최댓값)은 2의 16.xx승 이므로 18개의 색깔이면 충분하다는것을 이용해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> adj[100001];
int cache[100001][19]; //100000은 2의 16.xx승 이므로 18개의 색깔이면 충분하다
vector<int> maked_check(100001, 0);

void Pre()
{
	for (int i = 0; i < 100001; i++)
		for (int j = 0; j < 19; j++)
			cache[i][j] = -1;
}

struct node {
	int num;
	vector<node*> children;
};

//here가 루트인 서브트리 만들기
node* Make_tree(int here)
{
	node* ret = new node();
	ret->num = here;

	maked_check[here] = 1;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		if (maked_check[there] == 0)
		{
			ret->children.push_back(Make_tree(there));
		}
	}

	return ret;
}

//here를 color색으로 칠할때 비용
int Solve(node* here, int color)
{
	if (cache[here->num][color] != -1)
		return cache[here->num][color];

	int& here_cost = cache[here->num][color];

	here_cost = 0;
	here_cost += color;

	for (int i = 0; i < here->children.size(); i++)
	{
		node* there = (here->children)[i];
		int there_cost = 987654321;

		for (int j = 1; j <= min(18, n); j++)
		{
			//there에 칠할 색이 here이랑 같은 색일때
			if (color == j)
				continue;

			there_cost = min(there_cost, Solve(there, j));
		}

		here_cost += there_cost;
	}

	return here_cost;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	node* root = Make_tree(1); //1이 루트인 트리 만들기

	int result = 987654321;

	//100000(n의 최댓값)은 2의 16.xx승 이므로 18개의 색깔이면 충분하다
	for (int i = 1; i <= min(18, n); i++)
	{
		//루트를 i색으로 칠할때의 비용
		result = min(result, Solve(root, i));
	}

	cout << result;

	return 0;
}