C++로 트리에서 세 노드를 연결하는 경로의 노드 수가 최대가 되는 삼중항 찾기

개요

이 튜토리얼에서는 트리에서 세 개의 노드로 이루어진 삼중항(triplet)을 찾되, 이 세 노드를 서로 연결하는 경로가 커버하는 노드의 수가 최대가 되도록 만드는 프로그램을 살펴봅니다.

N개의 노드로 구성된 트리가 주어집니다. 우리의 과제는 세 노드를 연결하는 경로 위에 놓인 노드의 수가 최대가 되는 노드 조합을 찾는 것입니다.

접근 방법

이 문제는 트리의 지름(diameter), 즉 트리 내에서 가장 긴 경로를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

임의의 노드에서 DFS를 수행하여 가장 멀리 있는 노드(startnode)를 찾습니다.
startnode에서 다시 DFS를 수행하면서 각 노드의 부모를 기록합니다. 이때 가장 깊은 위치에 도달한 노드가 endnode이며, startnode와 endnode를 잇는 경로가 트리의 지름이 됩니다.
지름 경로에 포함된 모든 노드를 방문 처리(vis)합니다.
지름 경로 위의 각 노드에서 출발하여, 지름에 속하지 않는 방향으로 가장 깊이 뻗어 있는 노드(midNode)를 추가로 탐색합니다.

최종적으로 얻어진 세 노드 (startnode, endnode, midNode)가 바로 원하는 삼중항입니다. 지름의 양 끝점과 여기서 뻗어 나오는 가장 긴 가지를 함께 선택하면, 세 노드를 잇는 경로가 트리 전체에서 가장 많은 노드를 커버하게 됩니다.

예제 코드

#include <bits/stdc++.h>
#define ll long long int
#define MAX 100005
using namespace std;
vector<int> nearNode[MAX];
bool isTraversed[MAX];
//필요한 노드들을 저장
int maxi = -1, N;
int parent[MAX];
bool vis[MAX];
int startnode, endnode, midNode;
//노드 탐색을 위한 DFS 구현
void performDFS(int u, int count) {
    isTraversed[u] = true;
    int temp = 0;
    for (int i = 0; i < nearNode[u].size(); i++) {
        if (!isTraversed[nearNode[u][i]]) {
            temp++;
            performDFS(nearNode[u][i], count + 1);
        }
    }
    if (temp == 0) {
        if (maxi < count) {
            maxi = count;
            startnode = u;
        }
    }
}
void performDFS2(int u, int count) {
    isTraversed[u] = true;
    int temp = 0;
    for (int i = 0; i < nearNode[u].size(); i++) {
        if (!isTraversed[nearNode[u][i]] && !vis[nearNode[u][i]]) {
            temp++;
            performDFS2(nearNode[u][i], count + 1);
        }
    }
    if (temp == 0) {
        if (maxi < count) {
            maxi = count;
            midNode = u;
        }
    }
}
//트리 지름의 끝 노드 찾기
void performDFS1(int u, int count) {
    isTraversed[u] = true;
    int temp = 0;
    for (int i = 0; i < nearNode[u].size(); i++) {
        if (!isTraversed[nearNode[u][i]]) {
            temp++;
            parent[nearNode[u][i]] = u;
            performDFS1(nearNode[u][i], count + 1);
        }
    }
    if (temp == 0) {
        if (maxi < count) {
            maxi = count;
            endnode = u;
        }
    }
}
void calcTreeVertices() {
    performDFS(1, 0);
    for (int i = 0; i <= N; i++)
        isTraversed[i] = false;
    maxi = -1;
    performDFS1(startnode, 0);
    for (int i = 0; i <= N; i++)
        isTraversed[i] = false;
    int x = endnode;
    vis[startnode] = true;
    while (x != startnode) {
        vis[x] = true;
        x = parent[x];
    }
    maxi = -1;
    for (int i = 1; i <= N; i++) {
        if (vis[i])
            performDFS2(i, 0);
    }
}
int main() {
    N = 4;
    nearNode[1].push_back(6);
    nearNode[2].push_back(0);
    nearNode[1].push_back(7);
    nearNode[3].push_back(0);
    nearNode[1].push_back(2);
    nearNode[4].push_back(0);
    calcTreeVertices();
    cout << "Nodes: (" << startnode << ", " << endnode << ", " << midNode << ")";
    return 0;
}

출력 결과

Nodes: (0, 0, 0)

시간 및 공간 복잡도

위 알고리즘은 DFS를 몇 차례만 수행하면 되므로 시간 복잡도는 O(N)입니다. 인접 리스트와 방문 여부 배열 등을 저장하는 데 O(N)의 공간이 사용되므로 공간 복잡도 역시 O(N)입니다.