1967 트리의 지름

1967 트리의 지름 (c++)

문제

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

접근 방식

Tree, Post Order Traversal

1. 트리가 가지는 자식들 중 가장 긴 자식과, 다음으로 긴 자식을 더한다.
2. 그 값이 최대 길이보다 크면 최신화
3. 가장 긴 자식을 리턴
4. 1~3을 루트까지 반복 (자식 먼저 접근하고 부모를 접근하기 때문에 Post Order Traversal)

문제 풀이

#include <iostream>
#include <vector>
using namespace std;
inline int Max(int a, int b) { return a > b ? a : b; }
int N, a, b, c;
vector<pair<int, int>> v[10'005];
int maxTreeSize = 0;

int PostOrder(int root)
{
    int maxTree = 0, subTree = 0;
    for (int i = 0; i < v[root].size(); ++i)
    {
        int now = PostOrder(v[root][i].first) + v[root][i].second;
        if (maxTree <= now)
        {
            subTree = maxTree;
            maxTree = now;
        }
        else if (!subTree) subTree = now;
    }
    maxTreeSize = Max(maxTreeSize, maxTree + subTree);
    return maxTree;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;

    while (N-- > 1)
    {
        cin >> a >> b >> c;
        v[a].push_back({ b, c });
    }
    PostOrder(1);
    cout << maxTreeSize << endl;

    return 0;
}

다시 생각해 볼 점

1. 처음에 이중트리인줄 알고 풀었었는데, 틀려서 질문들을 찾아봤더니 이중트리가 아니였다.
   (당연하다고 생각하고 넘기지 말고 찬찬히 살펴보자)
2. 트리의 자식들을 저장하는 배열 vector<vector> v, 와 해당 노드로의 비용을 저장하는 배열 arr[10'001] 을 썼었는데, 해당 노드의 자식과 코스트를 저장하는 배열 vector<pair<int,int>> v를 [10'001]개만큼 만들면 해결되는 문제였다. (굳이 따로 쓸 필요 없음, 접근도 더 용이)