[백준 15942번] 전단지 돌리기 (C++)

문제링크 : https://www.acmicpc.net/problem/19542

19542번: 전단지 돌리기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, S, D, result = 0;
vector<int>arr[100001];
int depth[100001];
bool check[100001];

int dfs(int n)
{
    check[n]=true;

    for(int i=0; i<arr[n].size(); i++)
    {
        int next = arr[n][i];
        if(check[next]) continue;
        depth[n] = max(depth[n], dfs(next)+1); //다음 값이 존재하면 깊이 증가 
    }

    if(depth[n]>=D && n!=S)  //깊이가 D이상이면 무조건 가능, 시작점은 카운트 제외
    {
        result++;
    }

    return depth[n]; //깊이 반환
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> S >> D;

    for(int i=0; i<N-1; i++)
    {
        int x, y;
        cin >> x >> y;
        arr[x].push_back(y);
        arr[y].push_back(x);
    }
    
    dfs(S);

    cout << result * 2;  //왕복이므로 * 2
    
    return 0;
}

각 노드에 대해서 깊이를 계산하여 저장해준다.

만약 깊이가 D 이상이라면 무조건 가는 곳이다.

 

예제를 보면

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

1 -> 2 -> 3 -> 5 -> 6

   -> 4

 

1의 깊이 : 4

2의 깊이 : 3

3의 깊이 : 2

5의 깊이 : 1

4, 6의 깊이 : 0

인 것을 알 수 있다.

 

깊이가 D이상이라는 것은 해당 깊이 ~  D만큼의 깊이까지이다.

이렇게 깊이가 D인 곳까지는 직접 가서 전단지를 돌려준다.

깊이가 D인 곳 부터는 D만큼의 힘으로 전단지를 돌릴 수 있으므로 모든 곳에 전단지를 돌리는 것이 가능하다.

 

결국 깊이가 D이상인 노드만 체크하면 된다.

이때 시작점은 카운트하면 안되기에 S랑 같으면 안된다는 것을 적어준다.

 

이렇게 구한 값은 깊이가 D이상 값만 카운트 즉, 편도루트만 계산한 것이다.

배달하고 나서 다시 돌아와야하므로 카운트를 센 것에 * 2를 해준다.