[BOJ] 1967 - 트리의 지름 (C++)

문제

트리의 지름

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <unordered_map>

using namespace std;

int N, M = -1, far = 0;
unordered_map<int, vector< pair<int, int> > > adj;
bool visited[10000];

void dfs(int cur, int cnt){
    visited[cur] = true;
    
    if (M < cnt) {
        M = cnt;
        far = cur;
    }
    for (int i = 0; i < adj[cur].size(); i++){
        int next = adj[cur][i].first, val = adj[cur][i].second;
        if (visited[next]) continue;
        dfs(next, cnt+val);
    }
    visited[cur] = false;
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N;
    int x, y, val;
    for (int i = 0; i < N-1; i++){
        cin >> x >> y >> val;
        adj[x].push_back(make_pair(y, val));
        adj[y].push_back(make_pair(x, val));
    }
    
    dfs(1, 0);
    M = -1; memset(visited, false, sizeof(visited));
    dfs(far, 0);
    
    cout << M;
    return 0;
}

접근

지름을 구하기 위해서 한 노드에서 리프노드까지 도달하는 값의 합을 모두 살펴보았는데 이런 경우 시간초과가 발생하였다. 그래서 이 문제는 다른 분이 정리한 것을 참고하였다. 트리의 지름을 구하는 문제는 풀이법이 알려진 문제라고 한다. 이 풀이법을 근간으로 코드를 다시 작성하였고 통과할 수 있었다.

간단하게만 보면 지름을 구하는 방법은 아래와 같다.

1. 트리에서 임의의 정점 x를 잡는다.
2. 정점 x에서 가장 먼 정점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.

이 문제에서는 루트 노드가 1로 가정하였기 때문에 임의의 정점 x를 1로 설정하였고 이후 과정을 진행하였다.