백준 1967 / 트리의 지름

접근은 쉬웠지만 구현이 어려웠던 문제.

처음엔 DFS로 풀어보려 시도했으나 (많은 분들이 DFS로 푸셨더라)

시간초과가 자꾸 발생했다.

이유는 맨 밑 자식 노드들 중에서 경로가 가장 긴 자식 노드를 찾고, 

그 노드에서 다른 자식 노드들까지의 경로 중 최대값을 구하는 코드였는데

시간 복잡도가 O(N^3)가 나오기때문.

그리하여 BFS로 바꾸어 풀었다.

루트에서 가장 경로가 긴 노드를 찾고

그 노드에서 가장 멀리 있는 노드를 찾는 코드다.

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<memory.h>
#include<algorithm>
 
using namespace std;
 
int n;
 
vector<vector<int>>link;
vector<vector<int>>link2;
vector<int>son;
vector<int>ans;
 
bool check[10001];
int dist[10001];
 
void bfs(int from) {
    memset(dist, 0, sizeof(dist));
    memset(check, false, sizeof(check));
 
    queue<int>q;
    q.push(from);
    check[from] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        for (int i = 0; i < link[x].size(); i++) {
            int to = link[x][i];
            int cost = link2[x][i];
 
            if (check[to] == false) {
                check[to] = true;
                dist[to] = dist[x] + cost;
                q.push(to);
 
            }
        }
    }
}
int main() {
 
    //freopen("Text.txt", "r", stdin);
    cin >> n;
 
    link.resize(n + 1);
    link2.resize(n + 1);
 
    for (int i = 0; i < n - 1; i++) {
        int a, b, len;
 
        scanf("%d %d %d", &a, &b, &len);
 
        link[a].push_back(b);
        link2[a].push_back(len);
        link[b].push_back(a);
        link2[b].push_back(len);
    }
 
    bfs(1);
    
    int highest = 1;
 
    for (int i = 1; i <= n; i++) {
        if (dist[highest] < dist[i]) {
            highest = i;
        }
    }
    
    bfs(highest);
 
    int ans = -1;
 
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dist[i]);
    }
 
    cout << ans;
 
}