[백준 25516번] 거리가 k이하인 트리 노드에서 사과 수확하기 (C++)

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

25516번: 거리가 k이하인 트리 노드에서 사과 수확하기

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

int N, K, p, c, result;
vector<int>v[100001];
int arr[100001];

void dfs(int node, int dist)
{
    if(dist>K) return;
    result+=arr[node]; //사과 더해주기
    for(int i=0; i<v[node].size(); i++)
    {
        dfs(v[node][i], dist+1); //다음값 및 거리 증가
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> K;
    for(int i=0; i<N-1; i++)
    {
        cin >> p >> c;
        v[p].push_back(c);
    }
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }
    dfs(0, 0);
    cout << result;
}

간단한 dfs 및 bfs로 풀 수 있는 문제이다.

dfs 탐색시 현재 진행한 거리도 같이 넘겨준다. (K 체크)

 

그리고 다음 위치로 이동할때마다 해당 위치에 있는 사과를 더해주고, 현재 거리가 K를 넘겼으면 더해준 사과를 출력해주면 된다.