[C++] 백준 1967번: 트리의 지름

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

• 트리의 지름 찾기: 아무 점에서 가장 멀리 가는 점을 찾고, 그 점에서 가장 멀리 가는 점을 찾으면 끝! 친구한테 문어 인형으로 설명해줬던 기억이 난다.
• 문어 인형의 아무 다리나 잡고 높이 들어서 가장 멀리 있는 다리를 찾고, 그 다리를 잡고 다시 높이 들어서 가장 멀리 있는 다리를 찾아서 이으면 그게 트리의 지름이었다고 했었는데 덕분에 나도 기억이 난다
• 이 문제는 가중치가 있기 때문에 어느 점이든(나는 루트로 했다) DFS를 해서 가중치가 가장 높은 경로를 선택하고, 해당 정점에서 다시 가중치가 가장 높은 경로를 구하면 되고, 이때 구한 경로의 가중치의 합이 답이 된다.

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0); cin.sync_with_stdio(0)
#define SIZE 10003
int N, T, X, Y, W, M, costs,target;
// (가중치,다음 노드)
vector<pair<int, int>> Tree[SIZE];
bool visited[SIZE];
void init() {
    memset(visited, false, sizeof(visited));
}
void input() {
    cin >> N;
    M = N - 1;
    // 루트에서 DFS 해서 가장 긴 곳 찾고,
    // 거기서부터 다시 DFS 해서 가장 긴 곳 찾기 = 답
    // 
    for (int i = 0; i < M; i++)
    {
        cin >> X >> Y >> W;
        Tree[X].push_back({ W,Y });
        Tree[Y].push_back({ W,X });
    }
}
void dfs(int cur,int cost,int pre)
{

    if (costs < cost) {
        costs = cost;
        target = cur;
    }
    for (auto nxt : Tree[cur])
    {
        int w = nxt.first;
        int v = nxt.second;
        if (v == pre) continue;
        dfs(v, cost + w, cur);    

    }
}
int solve() {

    dfs(1, 0, 1);
    costs = 0;
    init();
    dfs(target, 0, target);
    return costs;
}
int main() {

    fastio;
        init();
        input();
        cout << solve();

}