백준 15458 : Barn Painting

문제 링크

트리와 이미 칠해진 지점의 색깔이 주어질 때, 3가지 색을 이용하여 트리를 인접한 정점끼리는 다른 색을 가지도록 칠하는 경우의 수를 구하는 문제이다.

이러한 문제는 트리 dp를 이용할 때 단골문제처럼 나왔던 문제였다.

dp[cur][color] = cur에서 color을 칠했을 때 cur ~ cur 자식들 에 대해 나올 수 있는 경우의 수 로 정의했고,

이미 칠해진 경우에 대해서는 already 배열을 정의하여 사용하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>

using namespace std;

typedef long long ll;

const int mod = 1e9+7;
const int INF = 987654321;

int n,k;
vector<vector<int>> edge;
vector<bool> isend;
vector<vector<ll>> dp;
vector<int> already;

void DFS(int cur,int prev)
{
	if(isend[cur])
	{
		for(int x = 0;x<3;x++)
		{
			if(already[cur] == -1 || already[cur] == x) 
			{
				dp[cur][x] = 1;
			}	
		}
		
		return;
	}
	
	for(auto next : edge[cur])
	{
		if(next != prev) DFS(next,cur);
	}
	
	for(int c = 0;c<3;c++)
	{
		if(already[cur] == -1 || already[cur] == c)
		{
			ll temp = 1;
		
			for(auto next : edge[cur])
			{
				if(next != prev)
				{
					ll clrdp = 0;
					for(int x = 0;x<3;x++)
					{
						if(x == c) continue;
						
						clrdp += dp[next][x];			
					}
					
					temp *= clrdp;
					temp %= mod;
				}
			}
			
			dp[cur][c] = temp;		
		}
	}		
}


int main(int argc, char** argv) {
	scanf("%d %d",&n,&k);
	
	dp = vector<vector<ll>>(n,vector<ll>(3,0));	
	edge = vector<vector<int>>(n);
	isend = vector<bool>(n,false);
	already = vector<int>(n,-1);
	
	for(int i = 0;i<n-1;i++)
	{
		int v1,v2;
		scanf("%d %d",&v1,&v2);
		
		v1--; v2--;
		edge[v1].push_back(v2);
		edge[v2].push_back(v1);
	}
	
	for(int i= 1;i<n;i++)
	{
		if(edge[i].size() == 1) isend[i] = true;
	}
	
	for(int i = 0;i<k;i++)
	{
		int v,c;
		scanf("%d %d",&v,&c);
		v--; c--;
		already[v] = c;
	}
	
	DFS(0,0);
	

	cout<<(dp[0][0] + dp[0][1] + dp[0][2]) % mod;
	return 0;
}
​