[BOJ / 트리 DFS] 19542 전단지 돌리기

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

19542번: 전단지 돌리기

 

19542 전단지 돌리기

알고리즘 : 트리 / DFS

현재 정점이 루트인지와 자식의 수에 따른 재귀의 갈래를 나누어주면 됩니다.

 

 

 

 

 

< CODE >

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define MAX 100005

vector<int> inj[MAX];

int n,s,d;

int dfs(int v, int last)
{
	if((inj[v].size() == 2 && last != -1) || (inj[v].size() == 1 && last == -1))
	{
		int to = inj[v][0];
		
		if(to == last)
			to = inj[v][1];
		
		int ret = dfs(to, v) + 1;
		return ret;
	}
	else if(inj[v].size() - 1 <= 0)
		return -d + 1;
	else
	{
		int ret = 0;
		int minus = -987654321;
		
		for(int i = 0; i < inj[v].size(); i++)
		{
			int to = inj[v][i];
			
			if(to == last)
				continue;
			
			int temp = dfs(to, v);
			
			if(temp <= 0)
				minus = max(minus, temp);
			else if(temp > 0)
				ret += temp;
		}
		
		if(ret <= 0)
			return minus + 1;
		
		return ret + 1;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> s >> d;
	
	for(int i = 0; i < n-1; i++)
	{
		int f,t;
		
		cin >> f >> t;
		
		inj[f].push_back(t);
		inj[t].push_back(f);
	}
	
	int result = dfs(s,-1);
	
	if(result <= 0)
		cout << "0\n";
	else
		cout << (result - 1) *2 << '\n';
	
	return 0;
}

시간 : 44ms

 

태그 : #BOJ 전단지돌리기 #백준 전단지돌리기 #전단지돌리기 풀이 #19542 전단지돌리기