BOJ 1967 - 트리의 지름(tree 구현, 순회, dfs)

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

1967번: 트리의 지름

- 간선의 가중치가 있는 트리에서 서로 가장 먼 노드의 거리를 구하는 문제이다. 

최장 경로의 양 끝 노드가 항상 root 이거나 leaf node여야 한다. 따라서 2가지 케이스를 따져야한다.

1. 가장 긴 root-leaf 경로의 길이(즉 트리의 height) 
2. 가장 긴 leaf-leaf 경로의 길이

풀이 : dfs 방식

이진트리이기 때문에 노드를 pair로 선언해서 to, weight를 입력해준다

특정 노드(서브 트리의 루트)에서 다른 노드로 가는 거리 중 가장 큰 경로를 dist배열에 저장한다.
그리고 그 노드에서 갈 수 있는 제일 긴 루트, 두 번째로 긴 루트를 찾아서 더한 뒤 ans와 비교한다.

그리고 leaf-leaf가 아닌 서브트리의 root-leaf 경로도 가장 긴 루트가 될 수 있으므로 dist배열의 값들과 ans를 비교해준다. 

 

#include <cstring>
#include <iostream>
#include <vector>
#define pii pair<int, int>
using namespace std;

// 1. root - leaf
// 2. leaf - leaf

// 모든 노드를 돌면서 제일 긴 depth를 찾고,
// 그 루트 노드로부터 다음 긴 depth의 leaf 노드를 찾는다
int n, ans;
vector<pii> tree[10001];  // to, weight;
int dist[10001];
bool check[10001];

void dfs(int u) {  // u -> v;
    int fi = -1, se = -1;
    for (pii node : tree[u]) {
        int to = node.first, w = node.second;
        if (!check[to]) dfs(to);

        int tmp = dist[to] + w;
        dist[u] = max(dist[u], tmp);

        if (fi < tmp) {
            se = fi;
            fi = tmp;
        } else if (se < tmp) {
            se = tmp;
        }
    }

    if (se != -1) {
        ans = max(ans, fi + se);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        tree[u].push_back({v, w});
    }

    dfs(1);                         // 1~n 탐색
    for (int i = 1; i <= n; ++i) {  // root-leaf가 지름인 경우
        ans = max(ans, dist[i]);
    }
    cout << ans;

    return 0;
}