1167번: 트리의 지름

시작점을 어디로 잡아도 상관없다.

선택한 시작점에서 가장 깊은 곳을 찾아낸 후 그곳에서 최대 지름을 구한다.

(처음 주어진 시작점이 가장 깊은 곳이 아닐수도 있다는 것에 숙지하고 있어야한다)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
 
 
std::vector<std::pair<int, int>> val[100001];
bool check[100001] = { false };
int max = 0, final = 0;
 
void BFS(int pos) {
    std::queue<std::pair<int, int>> mQueue;
    mQueue.push({ pos, 0 });
    check[pos] = true;
 
    while (!mQueue.empty()) {
        int front = mQueue.front().first;
        int count = mQueue.front().second;
        mQueue.pop();
 
        if (count > max) {
            max = count;
            final = front;
        }
 
        for (int i = 0; i < val[front].size(); i++) {
            if (!check[val[front][i].first]) {
                check[val[front][i].first] = true;
                mQueue.push({ val[front][i].first, count + val[front][i].second });
            }
        }
    }
}
 
 
int main(void) {
    int len;
    std::cin >> len;
 
    int pos, cur, distance;
    for (int i = 1; i <= len; i++) {
        std::cin >> pos;
        while (true) {
            std::cin >> cur;
            if (cur == -1) {
                break;
            }
            std::cin >> distance;
            val[pos].push_back({ cur, distance });
        }
    }
 
    BFS(pos);
    memset(check, false, sizeof(check));
    BFS(final);
 
    std::cout << max << "\n";
    return 0;
}