1167_트리의 지름

이 문제는 두개의 BFS를 이용하여 푸는 문제이다. 아무점이나 선택하여 BFS를 돌려 제일 먼 거리를 구한다. 그 다음 그 먼거리의 점에서 BFS를 돌려 제일 먼 거리를 구해주면 된다. 이것에 대한 증명을 고수들이 하던데, 나는 아직 증명까지는 잘 못하겠다. 여튼 BFS 두개를 돌려 해결한 문제이다.

문제 해결 과정 시작점과 어떤 자료구조에 대해 넣을지 고민을 하였다. 시작점은 BFS를 이용하여 구하였고, 자료구조는 vector<pair<int, int>> p[100001] 형태로 만들어주어 p[p1] = { p2, len} 로 표현되도록 하였다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
vector<pair<int, int>> tr[100001];
bool visited[100001];
int sum[100001];
int n, to, from, len, res, total;
int mPos, mVal;
void bfs(int node){
    queue<int> q;
    q.push(node);
    while(q.size()){
        int parent = q.front();
        visited[parent] = 1;
        for(pair<int, int> p :tr[parent]){
            if(!visited[p.first]){
                q.push(p.first);
                sum[p.first] = sum[parent] + p.second;
                if(mVal < sum[p.first]){
                    mVal = sum[p.first];
                    mPos = p.first;
                }
            }
        }
        q.pop();
    }
}
 
int main(void){
 
    cin >> n;
    for(int i = 0;i < n; i++){
        cin >> to;
        while(true){
            cin >> from;
            if(from == -1) break;
            cin >> len;
            tr[to].push_back(make_pair(from, len));
        }
    }
    bfs(1);
    memset(visited, 0, sizeof(visited));
    memset(sum, 0, sizeof(sum));
    mVal = 0;
    bfs(mPos);
    cout << mVal;
}