트리의 지름 (BOJ 2132)

망고·2024년 2월 16일

알고리즘

BOJ

목록 보기

2/11

문제

나무 위의 벌레

트리의 지름

개념

트리에서 가장 멀리 떨어진 정점 사이의 거리는
임의의 점 x,
x에서 가장 먼 거리에 있는 정점 y,
y와 가장 먼 거리에 있는 정점 z라 할 때
y와 z사이의 거리와 같다.

증명

트리 내에서 거리가 가장 먼 두 정점을 u와 v,
임의의 정점 x에서 가장 멀리 떨어진 점을 y라 할 때
가능한 경우는 아래와 같다.

1. x == u 혹은 y == v인 경우

2. dis(x, y)가 dis(u, v)와 특정 경로가 겹치는 경우

3. dis(x, y)와 dis(u, v)가 서로 독립적인 경우

알고리즘

1. 임의의 점(v1)에서 거리가 가장 먼 끝점(v10)을 구한다.

2. 해당 점(v10)에서 다시 거리가 가장 먼 점(v9)을 구한다.

3. 두 점 간의 거리는 트리에서 가장 길다. (트리의 지름)

코드 (boj 2132)

#include <bits/stdc++.h>

using namespace std;

int N, maxEat = INT_MIN;
vector<int> tree;
vector<int> starts;
vector<int> results;
vector<vector<int>> edge;


void input(){
    cin >> N;

    tree.push_back(-1);

    for(int i=1; i<=N; i++){
        int fruit;
        cin >> fruit;

        tree.push_back(fruit);
    }

    edge.resize(N+1);

    for(int i=0; i<N-1; i++){
        int to, from;

        cin >> to >> from;
        edge.at(to).push_back(from);
        edge.at(from).push_back(to);
    }
}

void buildStarts(int now, int prev, int eat){

    eat += tree.at(now);

    if(maxEat <= eat){
        if(maxEat < eat) starts.clear();

        maxEat = eat;
        starts.push_back(now);
    }

    vector<int> adj = edge.at(now);

    for(int i=0; i < adj.size(); i++){
        int next = adj.at(i);

        if(next != prev){
            buildStarts(next, now, eat);
        }
    }

    return ;
}
// 트리의 지름 위에 있는 vertex(starts)를 찾음


void buildEnds(int startVtx, int now, int prev, int eat){
    eat += tree.at(now);

    if(maxEat <= eat){
        if(maxEat < eat) results.clear();

        maxEat = eat;
        results.push_back(min(startVtx, now));
    }

    vector<int> adj = edge.at(now);

    for(int i=0; i < adj.size(); i++){
        int next = adj.at(i);

        if(next != prev){
            buildEnds(startVtx, next, now, eat);
        }
    }

    return;
}
// vertex(starts)에서 시작해 가장 먼 정점(results)을 구함


void outputStarts(){
    for(int i=0; i<starts.size(); i++){
        cout << starts.at(i) << " ";
    }
    cout << endl;
}

void output(){
    cout << maxEat << " " << results.at(0) <<endl;
}

void forEnds(){
    for(auto& startVtx : starts){
        buildEnds(startVtx, startVtx, 0, 0);
    }

    sort(results.begin(), results.end());
}

void run(){
    input();
    buildStarts(1, 0, 0);
    forEnds();
    output();
}

int main(){
    run();
    return 0;
}