[C++] 백준 19542번 전단지 돌리기

문제

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

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

출력

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

풀이

모든 노드를 순회하되 각 노드의 가장 멀리있는 자식을 구해 힘보다 작거나 같다면 해당 노드에는 접근 할 필요가 없다.
부모노드에 다시 방문하지 않기위해 매개변수로 parent를 추가했는데 visited배열에 방문 기록을 남기는 것이 더 깔끔한 것 같다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n,s,d;
vector<vector<int>> tree;
int dp[100001];

int getMaxDepth(int root, int parent){
  int &ret = dp[root];
  if (ret != -1) return ret;
  ret = 0;

  for (int i=0; i<tree[root].size(); i++){
    if (tree[root][i] == parent) continue;
    ret = max(ret, getMaxDepth(tree[root][i],root));
  }
  ret++;

  return ret;
}

int solve(int root, int parent){

  int ret = 0;

  for (int i=0; i<tree[root].size(); i++){
    if (tree[root][i] == parent) continue;
    if (getMaxDepth(tree[root][i],root) <= d) continue;

    ret += solve(tree[root][i],root)+1;
  }

  return ret;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n >> s >> d;
  tree.resize(n+2);

  for (int i=0; i<n-1; i++){
    int a,b;
    cin >> a >> b;

    tree[a].push_back(b);
    tree[b].push_back(a);
  }

  memset(dp, -1, sizeof(dp));

  cout << solve(s,-1)*2;
}