[BOJ 1167] 트리의 지름

🔗Link

문제
풀이

💡Idea

트리의 지름은 dfs를 2번 돌리면 되는 아주 유명한 문제이다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[100'000];

// 제일 먼 node, 그 거리
pair<int,int> dfs(int cur, int par){
    int farthest_node = cur, total_cost = 0;
    for(auto [nxt_node, curToNxt_cost]: adj[cur]){
        if(nxt_node == par) continue;
        auto [n, c] = dfs(nxt_node, cur);
        c+= curToNxt_cost;
        if(c > total_cost) {
            farthest_node = n;
            total_cost = c;
        }
    }
    return make_pair(farthest_node, total_cost);
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int V;

    cin >> V;

    int u, v, w;
    for(int i = 1; i <= V; i++){
        cin >> u >> v;
        while(v != -1){
            cin >> w;
            adj[u].emplace_back(v,w);
            cin >> v;
        }
    }

    auto [A, Ato1_cost] = dfs(1,-1);
    auto [B, AtoB_cost] = dfs(A,-1);

    cout << AtoB_cost;

    return 0;
}

🗨️ Side Notes

임의의 점 S로부터 가장 먼 점 A가 있을 때, A는 지름의 끝 점 중 하나이다.

만약 점 A가 지름의 끝 점이 아니라면, 지름의 끝 점을 U, V라고 할 때,

• U↔V 는 트리에서 가장 긴 경로
• A는 그 경로 바깥에 있거나 중간에 있음
• 따라서 A는 지름 끝점보다 멀어질 수 없다