[백준 1167번] 트리의 지름

문제 링크: https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

<문제 풀이> DFS

https://seokjin2.tistory.com/83

[백준 1967번] 트리의 지름

1967번 트리의 지름 문제에서는 N제한이 10,000이기 때문에 모든 정점에 대해서 DFS or BFS를 돌려서 O(N^2)에 트리의 지름을 구할 수 있었지만
이문제는 N제한이 100,000이기 때문에 O(N^2)을 하면 시간 초과가 나게 된다.

 

이문제는 모든 정점에 대해서 DFS를 호출하지 않고 DFS를 2번 호출해서 문제를 해결할 수 있다.

 

[트리의 지름 알고리즘]

1. 임의의 정점 x에서 가장 멀리 떨어진 정점 u를 찾는다

2. 1에서 찾은 정점 u에서 가장 멀리 떨어진 정점 v를 찾는다

3. u - v가 트리의 지름이 된다.

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
vector<pair<int, int> > adj[100001];
bool visited[100001];
int n;
int maxDist = 0;
int start = 0;
void dfs(int u, int dist) {
    visited[u] = true;
    if (dist > maxDist) {
        start = u;
        maxDist = dist;
    }
    for (auto v : adj[u]) {
        if (visited[v.first])continue;
        dfs(v.first, dist + v.second);
    }
}
 
void solve() {
    dfs(1, 0);
    maxDist = 0;
    fill(visited, visited + 100001, 0);
    dfs(start, 0);
    cout << maxDist;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u; cin >> u;
        while (true) {
            int v, c;
            cin >> v;
            if (v == -1) break;
            cin >> c;
            adj[u].push_back({ v, c });
        }
    }
    solve();
 
 
    return 0;
}