BOJ 1167번 트리의 지름

BOJ : https://www.acmicpc.net/problem/1167

github : https://github.com/junho0956/Algorithm/blob/master/1167/1167/%EC%86%8C%EC%8A%A4.cpp

 

앞전에 설명한 BOJ 1967번 트리의 지름과 같은 유형이지만

케이스의 증가로 일반적인 방법으로 풀면 시간초과가 된다.

BOJ 1967번을 설명하면서 언급했듯이 트리의 지름이라는 것을 이해하는 것이 우선이다.

 

임의의 리프노드를 출발으로 최대값을 찾으면 최대값을 만드는데 최종 결정을 한 노드를 알게되고

이 노드가 트리의 지름을 이루는 2개의 노드 중 1개가 된다는 것이다.

그럼 이 노드를 이용해서 다시 1번만 dfs 를 돌면 트리의 지름을 구할 수 있게 된다.

 

#include <iostream>
#include <vector>
using namespace std;
 
bool visit[100001];
vector<pair<int, int> > v[100001];
int N, f, s, w;
int Max_node, Max_total;
 
void dfs(int now, int total) {
    if (visit[now]) return;
    visit[now] = 1;
 
    if (Max_total < total) {
        Max_total = total;
        Max_node = now;
    }
 
    for (int i = 0; i < v[now].size(); i++) {
        dfs(v[now][i].first, total + v[now][i].second);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> f;
        while (1) {
            cin >> s;
            if (s == -1) break;
            cin >> w;
            v[f].push_back({ s,w });
            v[s].push_back({ f,w });
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (v[i].size() == 2) {
            dfs(i, 0);
            for (int i = 1; i <= N; i++) visit[i] = 0;
            dfs(Max_node, 0);
            break;
        }
    }
    
    cout << Max_total;
    return 0;
}