백준 15587 : Cow at Large(Gold)

문제 링크

N <= 100000인 트리가 주어질 때, 간선이 1개인 정점을 exit로 정의하고, 농부들은 exit에서 출발한다고 할 때, k에서 출발하는 Bessie를 잡기 위해 최소 몇 명의 농부가 필요한지 구하는 문제이다.

DP와 DFS를 이용하여 문제를 해결하였다.

트리에서 갈라지는 부분이 있다고 했을 때, Bessie가 이 교차점에 도달하는 시간보다 이 교차점의 자식 리프 노드에서 교차점으로 가는데 걸리는 시간이 더 짧다면, 그 교차점의 자식에 대해서는 한 명의 농부만 배치해도 모두 방어할 수 있다. 이 아이디어를 바탕으로 문제를 해결하였다.

DFS 함수가 현재 있는 지점에서 리프 노드까지 걸리는 최소 간선의 수(+1)를 리턴하도록 하고 만약 Bessie보다 먼저 도착할 수 있다면, dp[cur]을 1로, 아니라면 dp[cur] = 자식 노드의 dp들의 합으로 계산함으로써 해결하였다.

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

using namespace std;

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

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

int DFS(int cur,int prev)
{
	int ret = INF;
	
	if(isend[cur])
	{
		dp[cur] = 1;
		return 1;
	}
	
	for(auto next : edge[cur])
	{
		if(next != prev)
		{
			depth[next] = depth[cur] + 1;
			ret = min(ret,DFS(next,cur));
		}
	}
	
	if(depth[cur] >= ret)
	{
		dp[cur] = 1;
	}
	else
	{
		for(auto next : edge[cur])
		{
			if(next != prev)
			{
				dp[cur] += dp[next];
			}
		}
	}
	
	return ret+1;
}

int main(int argc, char** argv) {
	scanf("%d %d",&n,&k);
	
	k--;
	
	dp = vector<int>(n,0);
	edge = vector<vector<int>>(n);
	isend = vector<bool>(n,false);
	depth = vector<int>(n,0);
	
	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= 0;i<n;i++)
	{
		if(edge[i].size() == 1) isend[i] = true;
	}
	
	
	
	return 0;
}