C++로 트리에서 교차하지 않는 두 경로의 최대 곱 구하기

이 문제에서는 n개의 노드를 가진 무방향 연결 트리 T가 주어집니다. 우리의 목표는 C++을 이용해 이 트리 안에서 서로 교차하지 않는 두 경로(non-intersecting paths)의 길이 곱의 최댓값을 찾는 프로그램을 작성하는 것입니다.

문제 설명

트리 내에서 서로 겹치지 않는 모든 경로 쌍을 찾고, 각 경로의 길이를 곱한 값 중 가장 큰 값을 구해야 합니다.

예제로 이해하기

입력

그래프 —

출력

8

설명

교차하지 않는 경로 쌍으로 C-A-B와 F-E-D-G-H가 선택됩니다.

두 경로의 길이는 각각 2와 4이며, 따라서 곱은 2 × 4 = 8이 됩니다.

해결 접근 방법

이 문제는 DFS(깊이 우선 탐색)를 사용하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 트리를 DFS로 순회하면서, 특정 간선을 제거했을 때 나누어지는 두 개의 독립적인 부분 트리를 확인합니다.
2. 간선을 기준으로 양쪽 부분 트리에서 각각 가장 긴 경로의 길이를 계산합니다.
3. 두 경로의 길이를 곱한 값이 현재까지의 최댓값보다 크면 갱신합니다.
4. 모든 간선에 대해 위 과정을 반복하여 최대 곱을 구합니다.

즉, 하나의 간선을 잘라내면 트리가 두 개로 분리되므로, 각 분리된 영역에서의 최장 경로를 찾아 곱하면 교차하지 않는 두 경로의 곱을 얻을 수 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int TreeTraverse(vector<int> graph[], int& currPathMax, int val1, int val2){
    int max1 = 0, max2 = 0, maxVal = 0;
    for (int i = 0; i < graph[val1].size(); i++) {
        if (graph[val1][i] == val2)
            continue;
        maxVal = max(maxVal, TreeTraverse(graph, currPathMax,
          graph[val1][i], val1));
        if (currPathMax > max1) {
            max2 = max1;
            max1 = currPathMax;
        }
        else
            max2 = max(max2, currPathMax);
    }
    maxVal = max(maxVal, max1 + max2);
    currPathMax = max1 + 1;
    return maxVal;
}
int FindMaxProductPath(vector<int> graph[], int Size) {
    int maxProd = -10;
    int pathA, pathB;
    int currPathMax, prod;
    for (int i = 0; i < Size; i++) {
        for (int j = 0; j < graph[i].size(); j++){
            currPathMax = 0;
            pathA = TreeTraverse(graph, currPathMax, graph[i][j],i);
            currPathMax = 0;
            pathB = TreeTraverse(graph, currPathMax, i,graph[i][j]);
            prod = (pathA * pathB);
            maxProd = max(maxProd, prod);
        }
    }
    return maxProd;
}
void insertEdge(vector<int> graph[], int val1, int val2){
    graph[val1].push_back(val2);
    graph[val2].push_back(val1);
}
int main(){
    int Size = 8;
    vector<int> graph[Size + 2];
    insertEdge(graph, 1, 2);
    insertEdge(graph, 2, 4);
    insertEdge(graph, 3, 1);
    insertEdge(graph, 5, 4);
    insertEdge(graph, 7, 8);
    insertEdge(graph, 8, 4);
    insertEdge(graph, 5, 6);
    cout<<"Maximum product of two non-intersecting paths of tree is "<<FindMaxProductPath(graph, Size)<<"\n";
    return 0;
}

실행 결과

Maximum product of two non-intersecting paths of tree is 8

코드 동작 원리

• TreeTraverse 함수: DFS를 수행하며 현재 노드에서 뻗어 나가는 하위 경로들 중 가장 긴 두 경로(max1, max2)를 추적합니다. 두 경로의 합은 해당 노드를 지나는 최장 경로가 되며, 이를 재귀적으로 전파합니다.
• FindMaxProductPath 함수: 모든 간선에 대해 간선을 기준으로 양쪽 방향의 최장 경로(pathA, pathB)를 각각 구하고, 두 값의 곱이 최대가 되도록 갱신합니다.
• insertEdge 함수: 무방향 그래프이므로 양방향으로 간선 정보를 저장합니다.

이 알고리즘은 모든 간선에 대해 DFS를 수행하므로 시간 복잡도는 O(N²)입니다. 여기서 N은 트리의 노드 수입니다.