[BOJ] 19542 - 전단지 돌리기

[백준] 19542 - 전단지 돌리기

아이디어

아이디어는 간단하다. 말 그대로 한 번 DFS를 돌면서 루트로부터 현재 나의 레벨과, 내 자식들 중 가장 깊은 레벨을 탐색하고 그 차를 저장한 후 다시 그래프 탐색을 하며 차이가 D보다 클 때만 노드를 탐색하는 것이다.

문제

이렇게 간단하다고 말하면서 왜 문제를 못풀었었냐 하면.. 나는 N이 10만이기 때문에 편향트리가 주어진다면 DFS로는 이 문제를 풀 수 없다고 생각했다. 나는 C프로그램에서 재귀 스택은 최대 만단위 정도밖에 들어가지 못한다고 알고있었다.(사실 천단위라고 알고 있었는데 검색해보니 만단위라서 살짝 놀랐다.) 그래서 재귀를 통한 구현이 불가능해지자 다른 여러 방법을 시도했고 그 과정에서 시간초과와 많은 심적 고통을 받았는데.. DFS 코드가 통과되는 것으로 보아 다음의 두가지 경우를 생각해 볼 수 있을 것 같다.

1. C프로그램의 최대 재귀 깊이는 10만번까지도 수용 가능하다.
2. 해당 문제에서 최대N이 주어졌을 때 트리가 편향트리인 경우는 주어지지 않는다.

2번일 것이라고는 생각하지 않고 아마 1번이 맞지 않을까 추측해본다.. 생각보다 재귀가 여유있다는 것을 알게되어 나름 좋은 교훈이 된 문제였다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

vector<vector<int>> v;
bool ck[100005];
int level[100005];
queue<int> q;

int dfs(int now, int lev) {
	int rtn = lev;
	for (int next : v[now]) {
		if (!ck[next]) {
			ck[next] = true;
			rtn = max(rtn, dfs(next, lev + 1));
			ck[next] = false;
		}
	}
	level[now] = rtn - lev;
	return rtn;
}

int main(void) {
	int n, s, d, x, y;
	scanf("%d %d %d", &n, &s, &d);
	v.resize(n + 1);
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	ck[s] = true;
	dfs(s, 1);

	int ans = 0;
    memset(ck, 0, sizeof(ck));
	q.push(s);
	ck[s] = true;
	while (!q.empty()) {
		int now =q.front();
		q.pop();
		for (int next : v[now]) {
			if (ck[next] || level[next] < d) continue;
			ck[next] = true;
			ans += 2;
			q.push(next);
		}
	}
	printf("%d", ans);
	return 0;
}