백준 1167, 1967 트리의 지름 혼내주기

 

두 문제는 출력 형식만 다른 같은 문제다. 심지어 이름도 같다. 하나를 풀고 까먹을때쯤 다른 하나를 풀었어야 하는데, 눈앞에 꽁짜 경험치를 참지 못했다... 

 

문제를 딱 읽었을 때 방법이 떠오르지 않아서 시간초과가 분명함에도 모든 정점에서 bfs를 돌렸다. 물론 시간초과. 도저히 떠오르지 않아서 좀 찾아보니 구사과님의 블로그에 트리의 지름을 구하는 잡기술이 있었다.

 

1. 트리에서 임의의 정점 u에서 가장 먼 정점 v를 찾는다.
2. 정점 v에서 가장 먼 정점 w를 찾는다.

 

정점 v와 w를 찾았다면 트리의 지름은 v와 w의 거리이다. 남은 부분을 뚝딱하면 문제 해결.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int, int> > adj[100001];    //vertex distance
int v;

pair<int, int> bfs(int src){
    pair<int, int> ret = {src, 0};
    vector<int> visited(v+1, -1);
    queue<pair<int, int> > q;
    q.push({src, 0});
    visited[src] = 0;
    while(!q.empty()){
        int from = q.front().first, dist = q.front().second;
        q.pop();
        if(dist > ret.second){
            ret.first = from;
            ret.second = dist;
        }
        for(auto v : adj[from]){
            int to = v.first, nDist = dist + v.second;
            if(visited[to] >= 0) continue;
            q.push({to, nDist});
            visited[to] = nDist;
            
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int num, a, b;
    cin >> v;
    for(int i = 0; i < v; ++i){
        cin >> num;
        while(cin >> a && a != -1){
            cin >> b;
            adj[num].push_back({a, b});
        }
    }
    
    auto p = bfs(1);
    auto pp = bfs(p.first);
    
    cout << pp.second;
}