[BOJ] 19581 두 번째 트리의 지름

문제 요약

문제 링크: 백준 19581 - 두 번째 트리의 지름

문제 설명

 

---

접근 방법

기존 트리의 지름을 구하는 과정에서, 한 가지의 기믹을 추가하면 된다.

bfs 탐색함수의 매개변수 close로 특정 노드의 방문처리를 미리 해두는 것이다.

 

이를 활용하여, s에서 출발하지만 e로 향하지 않는 지름의 길이와 그 반대의 경우(e에서 출발하고 s로는 방문X) 지름의 길이를 비교해주면 두 번째로 긴 트리의 지름을 구할 수 있게 된다.

---

코드

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

int n;
vector<pair<int, int>>v[100001];

pair<int, int> bfs(int node, int close) {
    vector<bool>vis(n + 1, 0);
    if (close != -1) vis[close] = 1;  // 노드 방문처리로 연결 해제
    int mx = -1, ans = 0;
    queue<pair<int, int>>q;
    q.push({ node,0 });
    vis[node] = 1;
    while (q.size()) {
        int x = q.front().first;
        int sum = q.front().second;
        q.pop();
        if (mx < sum) {
            ans = x;
            mx = sum;
        }
        for (auto i : v[x]) {
            if (vis[i.first]) continue;
            q.push({ i.first,sum + i.second });
            vis[i.first] = 1;
        }
    }
    return { ans,mx };  // 가장 먼 노드와 그 가중치 합
}

void solve() {
    int s = bfs(1, -1).first;  // 임의의 한 노드(1)에서 가장 먼 노드 s
    int e = bfs(s, -1).first;  // s에서 가장 먼 노드 e
	
    // e를 한 점으로 하되 s를 방문처리한 지름과, s를 한 점으로 하되 e를 방문처리한 지름 비교
    cout << max(bfs(e, s).second, bfs(s, e).second);
}

void input() {
    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 main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}