[백준1967] 트리의 지름

• 트리의 지름 : 트리내의 최장경로를 찾는문제

 

IDEA

[부모노드를 포함하는 최장경로]

트리내의 모든 경로는 결국 부모노드를 기준으로 2개의 서브트리에서의 경로를 합친것이다.

 

 

위의 H-D-B-E-J 경로를 보면 B노드를 기준으로 왼쪽 자식 서브트리와 오른쪽 자식 서브트리의 경로를 합친거라고 생각할 수 있다. (이때 B노드와 같이 경로의 루트노드가 되는 노드를 최종 부모 노드라고 하겠다.)

 

최종부모노드 X의 경로 = (서브트리의 경로) - X - (서브트리의 경로)

 

즉, 최장 경로는 최종 부모노드의 서브트리 중, 가장 긴 경로는 가진 상위 2개의 경로에 최종부모노드를 합친 것이 된다.

 

 

위 그림에서 최종 부모 노드 A를 포함하는 최장 경로는 서버트리중 가장 긴 경로를 가진 B-D-I 경로와 C-F-M 경로를 합친 B-D-I-A-C-F-M이 되는 것이다.

int getDepth(int curr) {
    
    int ret = 0;
    
    for (int i=0; i<graph_node[curr].size(); ++i) {
        int node = graph_node[curr][i];
        int cost = graph_cost[curr][i];
        
        int curDepth = cost + getDepth(node);
        
        if (curDepth > depth[curr].first) {
            ret = curDepth;
            depth[curr].second = depth[curr].first;
            depth[curr].first = curDepth;
        } else if (curDepth > depth[curr].second) {
            depth[curr].second = curDepth;
        }
    }
    
    return ret;
}

위의 코드는 최종 부모 노드 curr을 기준으로, 자식 서브 트리들의 경로 중 가장 긴 경로 둘을 depth[curr]에 pair 자료구조로 저장한다.

즉, curr을 최종 부모 노드로 하는 최장 경로는 depth[curr].first + depth[curr].second가 된다.

코드를 보면 자신 노드를 들을 순환하면 자식 노드의 최장 경로(재귀탐색)에 간선의 가중치를 더한 값이 기존의 상위 2개의 최장경로보다 긴지 검사하여 값을 업데이트한다.

 

 

[step2. 트리의 최장경로]

트리의 최장경로는 그렇다면 [서브트리의 최장경로 - 루트노드 - 서브트리의 최장경로] 라고 생각하기 쉽지만 그렇지 않다. 서브트리내에 루트노드를 거치지 않는 최장경로가 존재할 수 있다.

 

 

이런 경로가 최장경로가 될 수도 있다.

그렇기 때문에 모든 노드를 대상으로 최종 부모노드로 하는 최장경로를 구해 그중 가장 긴 경로를 트리의 최장 경로로 결정한다.

int getRadius(int curr) {
    
    int ret = depth[curr].first + depth[curr].second; 
    
    for (int i=0; i<graph_node[curr].size(); ++i) {
        int node = graph_node[curr][i];
        int cost = graph_cost[curr][i];
        
        int radius = getRadius(node);
        if (radius > ret) ret = radius;
    }
    
    return ret;
}

getRadius는 curr을 루트노드로 하는 트리의 최장경로를 구한다.

일단 루트노드를 지나는 최장 경로는 getDepth()를 통해 구한 2개의 경로를 더한값이 된다.

그리고 자식 트리의 노드를 루트노드하는(즉, 현재 루트노드를 지나지 않는) 최장 경로를 구해 비교하여 최장 경로를 결정한다.

 

 

최종 코드

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<vector<int>> graph_node(10001);
vector<vector<int>> graph_cost(10001);
pair<int,int> depth[10001];

void init() {
    for (int i=1; i<10001; ++i) {
        depth[i] = make_pair(0,0);
    }
}

int getDepth(int curr) {
    
    int ret = 0;
    
    for (int i=0; i<graph_node[curr].size(); ++i) {
        int node = graph_node[curr][i];
        int cost = graph_cost[curr][i];
        
        int curDepth = cost + getDepth(node);
        
        if (curDepth > depth[curr].first) {
            ret = curDepth;
            depth[curr].second = depth[curr].first;
            depth[curr].first = curDepth;
        } else if (curDepth > depth[curr].second) {
            depth[curr].second = curDepth;
        }
    }
    
    return ret;
}

int getRadius(int curr) {
    
    int ret = depth[curr].first + depth[curr].second; 
    
    for (int i=0; i<graph_node[curr].size(); ++i) {
        int node = graph_node[curr][i];
        int cost = graph_cost[curr][i];
        
        int radius = getRadius(node);
        if (radius > ret) ret = radius;
    }
    
    return ret;
}

int main() {
    
    int n;
    cin >> n;
    init();
    
    for (int i=0; i<n-1; ++i) {
        int parent, child, cost;
        cin >> parent >> child >> cost;
        
        graph_node[parent].push_back(child);
        graph_cost[parent].push_back(cost);
    }
    
    getDepth(1);
    cout << getRadius(1);
}