[백준 1967번] 트리의 지름

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

1967번: 트리의 지름

<문제 풀이> DFS, BFS

N <= 10,000 이기 때문에 O(N^2)으로 문제를 해결할 수 있습니다.

모든 정점에 대해서 DFS or BFS를 돌려서 거리의 최댓값을 계속 갱신하면 됩니다.

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int n;
vector<pair<int, int> > adj[10001];
int dist[10001];
int res = 0;
void bfs() {
    for (int s = 1; s <= n; s++) {
        fill(dist, dist + 10001, -1);
        queue<int> Q;
        Q.push(s);
        dist[s] = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            res = max(res, dist[u]);
            for (auto& v : adj[u]) {
                if (dist[v.first] != -1) continue;
                dist[v.first] = dist[u] + v.second;
                Q.push(v.first);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({ v, c });
        adj[v].push_back({ u ,c });
    }
    bfs();
    cout << res;
    return 0;
}