백준(Baekjoon)문제 풀이 - 19542 전단지 돌리기(C++)

전단지 돌리기

문제

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

주어진 트리모양의 길 위에 전단지를 돌리는 문제이다. 힘을 나타내는 D보다 작은거리는 탐색하지 않고, 생각했을때의 최소 경로를 구해야되는 문제이다.

입출력 형식

<입력 형식>

첫째줄 노드의 수(1 <= N <= 100,000)과 시작점의 위치 S(1<= S <= N), 힘 D(0 <= D <= N)이 주어진다.

두번째줄부터 N째 줄까지, 트리의 간선정보가 주어진다.

 

<출력 형식>

최소 거리를 출력한다.

 

<입력 예>

6 1 1
1 2
2 3
2 4
3 5
5 6

<출력 예>

6

아이디어

 트리구조라는점, 최소경로를 찾아야되는 점에서 DFS라는 것을 어느정도 유추해 볼 수 있다. 그 후, 트리 형태의 그래프를 그려보자. 아래는 트리 형식의 그래프와 그에따른 deep을 나타낸 그래프이다.

위와 같이 deep을 채워주는 DFS를 한번 돌린다. 이때 deep은 가장 아래 노드부터 최상단의 노드까지 역으로 탐색하며, 깊이를 저장한 값이다. 이를 이용하면, 답을 쉽게 구할 수 있다. 다시 Deep이 D(힘)보다 큰 deep을 탐색하며, 이러한 deep값을 찾을 때 마다 ans++을 해주고, ans를 출력하면 될 것 이다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, s, d;
int deep[100010];
int ans = 0;
vector <int> vec[100010];
bool ch1[100010], ch2[100010];

void ans_find(int x)
{
	int i;
	for (i = 0; i < vec[x].size(); i++) {
		int now = vec[x][i];
		if (ch2[now] == 0 && deep[now] > d) {
			ans++;
			ch2[now] = 1;
			ans_find(now);
			ch2[now] = 0;
		}
	}
	return;
}

int deep_find(int x)
{
	int i, dep = 0;
	for (i = 0; i < vec[x].size(); i++) {
		int now = vec[x][i];
		if (ch1[now] == 1) continue;
		ch1[now] = 1;
		dep = max(dep, deep_find(now));
	}
	return deep[x] = max(dep, deep[x]) + 1;
}

int main()
{
	int i, j;
	scanf("%d %d %d", &n, &s, &d);
	for (i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
    ch1[s] = 1;
	deep_find(s);
    ch2[s] = 1;
	ans_find(s);
	printf("%d", ans * 2);
	return 0;
}