트리의 지름 1967

문제

접근 방법

자식 노드 중에서 가장 긴 값을 가져가면 된다.
하지만 가장 긴 값인지 어떻게 아는가?
그것은 가장 깊은 곳까지 확인해 보고 알 수 있다.
자신이 가진 자식 노드 중 가장 긴 값을 반환해 주는 방식으로 반복하면 루트에서부터 가장 긴 값이 반환될 것이다.

하지만 문제에서도 보여주듯 루트가 가장 긴 트리의 지름을 가지고 있는
상태가 아닐 수 있다.
반환하기 직전에 합산된 자식의 값이 최고점인지 갱신해 주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
vector<vector<pii>> graph;
vector<bool> isVisited;
int ret;
int dfs(int cur)
{
    int cnt = 0, sum = 0;
    isVisited[cur] = true;
    vector<int> buffer;
    for (pii next : graph[cur])
        if (!isVisited[next.first])
        {
            int child = dfs(next.first) + next.second;
            cnt = max(child, cnt);
            // DFS를 마친 값을 저장해 줘야 한다. (얼마나 긴 값인지 알아야 하므로)
            buffer.push_back(child);
        }
    if (buffer.size() <= 2) // 2개 이하인가?
        for (int i : buffer)
            sum += i;
    else
    {
        // 2개 이상이면 가장 큰 2개의 값을 더해준다.
        sort(buffer.begin(), buffer.end(), greater<int>());
        sum = buffer[0] + buffer[1];
    }
    // 가장 긴 트리의 지름인지 확인해 준다.
    ret = max(ret, sum);
    return cnt;
}
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, a, b, c;
    cin >> n;
    graph = vector<vector<pii>>(n + 1, vector<pii>());
    isVisited = vector<bool>(n + 1);
    while (--n)
    {
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
}
int main()
{
    input();
    dfs(1);
    cout << ret;
    return 0;
}

풀이

트리의 자식이 3개 이상일 수 있다. (이진 트리라는 말이 없다)
그러므로 DFS를 끝낸 자식의 값 중 가장 큰 2개의 값을 합산해서 가장 긴 트리의 지름인지 확인해 주면 된다.

나의 경우 DFS를 하기 전에 graph를 정렬하고 가장 높은 두 값을 활용하는 방식으로 했다가 틀렸다. 그렇게 하면 자식의 값이 합산되지 않는다. 당장 다음 정점까지의 길이가 1일지라도 밑에 숨은 값이 20인 경우를 놓칠 수 있는 것이다.