[백준 1967] - 트리의 지름(TREE, DFS) C++

문제

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

1967번: 트리의 지름

접근방법

트리의 지름 구하는 방법은

임의의 노드 x로부터 가장 먼 노드를 하나 선택하고

그 노드로부터 가장 먼 노드와의 거리를 측정하는 것이다.

 

문제의 그림을 보면 직관적으로 이해할 수 있다.

 

가장 먼 노드를 찾는 것과 가장 먼 노드와의 길이를 측정하기 위해서 DFS알고리즘을 이용했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>


using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define _FOR(i, s, n) for (int i=s;i<(n);++i)
#define INF 987654321

vector<vector<pair<int, int>>> adj_list;
vector<int> cache;      //from에서 to까지 거리
int n;
int far_dist = 0, far_node = 0;

//call하기전 cache 초기화 필수
//cache[from] = 0; 설정 필수
//far_dist, far_node 초기화
void find_far_node(int from) {
    int& ret = cache[from];
    if (far_dist < cache[from]) {
        far_dist = cache[from];
        far_node = from;
    }
    for (auto& adj : adj_list[from]) {
        if (cache[adj.first] != -1) continue;
        cache[adj.first] = cache[from] + adj.second;
        find_far_node(adj.first);
    }
}

void init(int from) {
    cache = vector<int>(n+1, -1);
    cache[from] = 0; far_dist = 0;
}

int main() {
    cin >> n;
    adj_list = vector<vector<pair<int, int>>>(n+1, vector<pair<int, int>>());
    FOR(i, n-1) {
        int from, to, dist;
        cin  >> from >> to >> dist;
        adj_list[from].push_back({to, dist});
        adj_list[to].push_back({from, dist});
    }
    init(1);
    find_far_node(1);
    init(far_node);
    find_far_node(far_node);
    cout << far_dist << endl;

    return 0;
}

개선할 점

..