백준 골드2 1167 트리의 지름 구하기

https://www.acmicpc.net/problem/1167

 
 
트리의 지름이라서 어떻게 구할까 했는데,
그냥 가장 긴 경로를 찾으면 된다.
 
임의의 노드 하나를 정해서
BFS로 탐색하면 그 중에서 가장 긴 노드를 찾아 그 노드 값을 저장한다.
어떤 정점까지가 더 긴가는,
해당 정점 수 만큼의 거리를 담은 배열로 비교한다.
 
가장 긴 경로를 가진 정점을 구했으면,
가장 긴 경로를 가진 정점에서 다시 출발한다.
거리를 담은 정점 배열에서,
도착지까지 가장 길었던 값을 가져오면
해당 정점의 최대 길이를 알 수 있다.
 
이 최대 거리가 트리의 지름이다.
 

using namespace std;

vector<bool> visited;
vector<int> mDistance;
typedef pair<int, int> edge;
vector<vector<edge>> tree;

void BFS(int node);

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);

    int v;
    int vertexNum = 0;

    cin >> v;

    tree.resize(v + 1);

    for(int i = 0; i < v; i++) {
        cin >> vertexNum;
        while (true)
        {
            int mvertex, distance;

            cin >> mvertex;

            if (mvertex == -1) break;

            cin >> distance;
            tree[vertexNum].emplace_back(edge(mvertex, distance));
        }
    }

    mDistance = vector<int>(v + 1, 0);
    visited = vector<bool>(v + 1, false);
    BFS(1);
    int max = 1;
    
    for (int i = 2; i <= v; i++) {
        if (mDistance[max] < mDistance[i])
            max = i;
    }
    fill(mDistance.begin(), mDistance.end(), 0);
    fill(visited.begin(), visited.end(), false);
    BFS(max);
    sort(mDistance.begin(), mDistance.end());
    cout << mDistance[v] << "\n";
    
    return 0;
}

void BFS(int node)
{
    queue<int> que;
    que.push(node);
    visited[node] = true;

    while (!que.empty())
    {
        int idx = que.front();
        que.pop();
        for (edge it : tree[idx]) {
            if (!visited[it.first]) {
                visited[it.first] = true;
                que.push(it.first);
                mDistance[it.first] = mDistance[idx] + it.second;
            }
        }
    }

    return;
}