백준[19581] 두 번째 트리의 지름

문제 설명

문제 링크

http://icpc.me/19581

19581번: 두 번째 트리의 지름

풀이

bfs/dfs를 이용하여 풀 수 있다.

임의의 점을 하나 잡고, 그 점에서 가장 먼 점을 구한다. 그때 이 가장 먼 점을 a라고 하자.

a에서 가장 먼 점을 구한다. 그때 이 점을 b라고 하자.

그럼 이때 a, b의 거리가 트리의 지름이 되고, 이 두 점이 트리에서 가장 먼 두 점이다.

그럼 이제 이 두 점 사이 거리를 제외한 가장 먼 거리를 찾아야하기 때문에, a에서 b를 제외한 가장 먼 거리를 구하고, b에서 a를 제외한 가장 먼 점을 구하면, 두번째 트리의 지름이 나온다.

코드

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<pair<int, int>> v[N];
queue<int> q;
bool visited[N];
int dist[N];

pair<int, int> bfs(int s, int rmv = 0) {
    memset(visited, false, sizeof(visited));
    memset(dist, 0, sizeof(dist));
    q.push(s);
    visited[rmv] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        visited[cur] = true;
        for (auto [nxt, d] : v[cur]) {
            if (visited[nxt]) continue;
            q.push(nxt);
            dist[nxt] = dist[cur] + d;
        }
    }
    int *ret = max_element(dist, dist + N);
    // 가장 큰 값의 인덱스, 가장 큰 값
    return {ret - dist, *ret};
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c; cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    int a = bfs(1).first;
    int b = bfs(a).first;
    cout << max(bfs(a, b).second, bfs(b, a).second);
}