C++에서 X와의 절대 차이가 최소인 트리 노드 찾기

트리와 각 노드의 가중치, 그리고 하나의 정수 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

노드 3의 절대 차이인 4가 다른 모든 노드보다 작으므로 정답은 노드 3이 됩니다.

문제 해결 접근 방식

풀이 아이디어는 매우 간단합니다. 트리 전체에 대해 DFS(깊이 우선 탐색)를 수행하면서, 현재까지 탐색한 노드 중 x와의 가중치 절대 차이가 최소인 노드를 계속 추적하면 됩니다. 탐색이 끝나면 그때까지 기록된 노드가 곧 정답입니다.

DFS 구현 시 부모 노드로 되돌아가는 것을 방지하기 위해 parent 파라미터를 활용하는 점도 핵심입니다.

C++ 구현 예제

#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

코드 설명

• min_value: 현재까지 발견한 최소 절대 차이를 저장하며, 초기값은 INT_MAX로 설정합니다.
• dfs 함수: 각 노드를 방문할 때마다 |weight[node] − x|를 계산하여 min_value보다 작으면 해당 값을 갱신하고 result에 노드 번호를 저장합니다.
• parent 체크: 인접 노드가 부모 노드와 같으면 재방문하지 않고 건너뛰어 무한 루프를 방지합니다.

이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)이며, N은 노드의 개수입니다.