[19542번] 전단지 돌리기

문제

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가 D 이하인 모든 노드에 전단지를 돌릴 수 있다.

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

입력

첫번째 줄에는 노드의 개수 N(1≤N≤100 000)과 케니소프트의 위치 S(1≤S≤N), 힘 D(0≤D≤N)이 주어진다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드가 연결되어 있음을 의미한다. (1≤x,y≤N, x≠y)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1이다.

출력

현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.

나의 답

#include <iostream>
#include <vector>
using namespace std;

int N, S, D;
vector<vector<int>> node;
int c = 0;
int r;

int DFS(int cur_node, int parent)
{
    int max_result = 0;
    if(node[cur_node].size()==1 && cur_node!=S) {
        if(D>0)
            r -= 2;
        return 0;
    }

    for(int i=0; i<node[cur_node].size(); ++i){
        if(node[cur_node][i]!=parent) {
            int result = DFS(node[cur_node][i], cur_node)+1;
            if(result > max_result)
                max_result = result;
        }
    }

    if(max_result != 0 && max_result < D && cur_node != S)
        r -= 2;

    return max_result;
}

int main(void)
{
    cin >> N >> S >> D;
    node.resize(N+1);
    for(int i = 0; i < N-1; ++i) {
        int x, y;
        cin >> x >> y;
        node[x].push_back(y);
        node[y].push_back(x);
    }

    r = (N-1)*2;
    DFS(S, 0);

    cout << r << endl;

    return 0;
}

출처

Contest > 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회 > UCPC 2020 A번