트리가 있고 모든 노드의 가중치와 정수 x가 있다고 가정합니다. |weight[i] - x|와 같은 노드 i를 찾아야 합니다. 최소입니다. 그래프가 아래와 같을 때 x =15
출력은 3이 됩니다. 이제 다른 노드의 경우 아래와 같을 것입니다.
노드 1, |5 – 15| =10
노드 2, |10 – 15| =5
노드 3, |11 – 15| =4
노드 4, |8 – 15| =7
노드 5, |6 – 15| =9
아이디어는 간단합니다. 우리는 트리에서 DFS를 수행하고 x와의 가중 절대 차이가 최소값을 제공하는 노드를 추적합니다.
예
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int min_value = INT_MAX, x, result;
vector<int> graph[100];
vector<int> weight(100);
void dfs(int node, int parent) {
if (min_value > abs(weight[node] - x)) {
min_value = abs(weight[node] - x);
result = node;
}
for (int to : graph[node]) {
if (to == parent)
continue;
dfs(to, node);
}
}
int main() {
x = 15;
weight[1] = 5;
weight[2] = 10;
weight[3] = 11;
weight[4] = 8;
weight[5] = 6;
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[1].push_back(5);
dfs(1, 1);
cout << "The node number is: " << result;
} 출력
The node number is: 3