[백준] 1967 트리의 지름

트리의 지름 구하는법을 들어만봤는데 이번에 처음으로 구해봤다

weeklyps.com을 보며 공부했다!

2가지 방법이 있는데 그리디를 이용하는게 쉽길래 그리디 이용 ㅎㅎ

방법은 간단한다

1. 임의의 정점 a에서 가장 먼~~ 정점 b를 찾는다

2. 그 후 찾은 정점 b에서 가장 먼~~ 정점 c를 찾는다

3. 그럼 b에서 c까지의 거리가 트리의 지름이 된다

증명은 복잡하므로 생략

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<pair<int, int>>> Graph;
int n, d[10010];
bool check[10010];
 
int dfs(int x) {
    check[x] = true;
    int ret = x;
    d[x] = 0;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i].first;
        int cost = Graph[x][i].second;
        if (check[next]) continue;
        int ret_next = dfs(next);
        if (d[x] < d[next] + cost) {
            d[x] = d[next] + cost;
            ret = ret_next;
        }
    }
    return ret;
}
int main() {
    scanf(" %d", &n);
    Graph.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; scanf(" %d %d %d", &u, &v, &w);
        u--; v--;
        Graph[u].push_back({ v,w });
        Graph[v].push_back({ u,w });
    }
    int s = dfs(0);
    memset(check, 0, sizeof(check));
    memset(d, 0, sizeof(d));
    int e = dfs(s);
    printf("%d\n", d[s]);
}