[ BOJ 백준 1967번 - 트리의 지름 ] 해설 및 코드

https://www.acmicpc.net/problem/1967

 

목적

두 노드 사이의 경로 길이의 최대값을 구하자.

 

접근법

1. DFS로 부분 트리의 자식 노드들을 살펴, 자식 노드를 거쳐 갈 수 있는 가장 긴 길이를 두 개를 더해 트리의 지름을 만들고 최대값을 갱신한다.

 

2. 가장 긴 길이는 반환 값으로 넘겨줘서, 그 값을 부모 트리에서 다시금 사용할 수 있게 한다.

 

 

#include<bits/stdc++.h>
using namespace std;
 
vector<pair<int, int>> t[10001]; 
int ans=0;
 
int sol(int i) {
    int a=0, b=0;
    for (auto e : t[i]) {
        int tmp = sol(e.first) + e.second;
        if (a < tmp)b = a, a = tmp;
        else if (b < tmp)b = tmp;
    }
    ans=max(ans,a+b);
    return a;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    while(--n){
        int a, b, c; cin >> a >> b >> c;
        t[a].push_back({ b,c });
    }
    sol(1);
    cout << ans;
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.