C++ 트리 간선 가중치 할당: 최장 경로의 길이를 최소화하는 방법

이 문제에서는 하나의 트리와 합계 S가 주어집니다. 우리가 해야 할 일은 나머지 모든 간선에 가중치를 할당하되, 가중치 기준으로 가장 긴 경로가 가능한 한 짧아지도록 만드는 것입니다. 단, 할당된 가중치의 총합은 반드시 S와 같아야 한다는 조건이 있습니다.

문제 해결 접근법

풀이 아이디어는 의외로 간단합니다. 결정적인 열쇠는 트리의 한 가지 성질, 즉 '트리의 어떤 경로에도 리프 노드는 최대 2개까지만 포함될 수 있다'는 사실입니다.

이 성질을 활용하면 다음과 같은 전략을 세울 수 있습니다.

• 리프 노드에 연결된 간선에만 가중치를 부여합니다.
• 나머지 모든 간선에는 0을 할당합니다.
• 리프 노드에 연결된 각 간선에는 S ÷ L(L은 리프 노드의 개수)의 가중치를 부여합니다.

하나의 경로에는 리프 노드가 최대 두 개까지 포함될 수 있으므로, 최종적으로 최장 경로의 길이는 다음 공식으로 계산됩니다.

최장 경로 길이 = 2 × (S ÷ L)

C++ 구현 예제

#include<iostream>
#include<vector>
using namespace std;
void insertEdge(int u, int v, vector<int> adj[]) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}
long double pathLength(vector<int> adj[], int sum, int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1)
            count++;
    }
    long double ans = 2.0 * (long double)(sum / (long double)(count));
    return ans;
}
int main() {
    int n = 6;
    vector<int> adj[n + 1];
    insertEdge(1, 2, adj);
    insertEdge(2, 3, adj);
    insertEdge(2, 4, adj);
    insertEdge(4, 5, adj);
    insertEdge(4, 6, adj);
    int sum = 1;
    cout << pathLength(adj, sum, n);
}

코드 설명:

• insertEdge(): 인접 리스트(adjacency list) 형태로 트리에 양방향 간선을 추가합니다.
• pathLength(): 차수(degree)가 1인 정점, 즉 리프 노드의 개수를 먼저 센 뒤, 앞서 살펴본 공식 2 × (S ÷ L)을 적용해 최장 경로의 길이를 반환합니다.
• main(): 6개의 노드로 구성된 트리를 생성하고 간선을 추가한 후, 총합 S = 1일 때의 결과를 출력합니다.

출력 결과

0.5

위 예제에서 리프 노드는 1, 3, 5, 6으로 총 4개입니다. 따라서 최장 경로의 길이는 2 × (1 ÷ 4) = 0.5가 되며, 이것이 주어진 조건 하에서 달성할 수 있는 최소값입니다.