알고리즘/BOJ

백준 25516번 거리가 K이하인 트리 노드에서 사과 수확하기

꾸준함. 2022. 9. 4. 18:58

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

 

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

n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 모든 간선의 길이는 1이다. 트리 T의 각 정점에는 사과가 0개 또는 1개 놓여있다. 루

www.acmicpc.net

간단한 DFS 문제였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100000;
int result;
int n, k;
int apples[MAX];
vector<int> graph[MAX];
void func(int node, int dist)
{
if (dist > k)
{
return;
}
result += apples[node];
for (int next : graph[node])
{
func(next, dist + 1);
}
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 0; i < n - 1; i++)
{
int p, c;
cin >> p >> c;
graph[p].push_back(c);
}
for (int i = 0; i < n; i++)
{
cin >> apples[i];
}
func(0, 0);
cout << result << "\n";
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형