[BOJ-1167]트리의지름

트리의 지름을 구하는 문제

어느 지점에서 시작해도 가장 먼 노드가 시작노드가 되며, 이때 1-BFS 를 사용하고,

두번째, 시작노드를 구했다면, 2-BFS 를 사용하여 "트리의 지름" 을 구한다. 

총 2번의 BFS를 사용하여 결과를 구할 수 있다.

먼저, 모든 입력을 받는다.

(1) 임의의 노드를 선택한다. (코드에선 1을 지정)

(2) (1)에 선택한 노드를 방문 표시한 후 Q에 넣는다.

(3) 1-BFS

1) Q에서 노드(here)를 꺼낸다. 

2) 꺼낸 노드(here)와 연결되어 있고, 방문하지 않은 노드(there.first)를 방문한다.

3) 방문한 노드의 이동 비용을 update 한 후, 노드방문표시, Q에 넣는다.

4) Q에 넣는 노드가 도달비용이 최대라면 max_node , max_cost를 업데이트 한다.

(4) 2-BFS 

(3) 의 과정을 완료하면, 시작노드를 구한 것이다. 시작노드부터 BFS를 하여 가장 먼 위치에 있는 노드와의 비용을 구한다.

(5) 비용을 출력한다.

#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
 
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
 
typedef long long lld;
typedef pair<lld, lld> PLL;
typedef pair<int, lld> PIL;
typedef vector<lld> VLL;
typedef vector<PLL> VPLL;
typedef vector<PIL> VPIL;
typedef vector<bool> VB;
 
VPIL graph[111111];
int main(){
    int n; scanf("%d",&n);
    
    for(int i = 0 ; i < n ; i++){
        int src; scanf("%d",&src);
        while(true){
            int dst;
            lld cos;
            scanf("%d", &dst);
            if(dst == -1) break;
            scanf("%lld", &cos);
            graph[src].pb(mp(dst,cos));
        }
    } // input end
 
    VB visited(n+1, false);
    queue<lld> Q;
    VLL cost(n+1, 0);
    Q.push(1);
    visited[1] = true;
    int max_node = 1;
    lld max_cost = -1;
    while(!Q.empty()){
        int here = Q.front(); Q.pop();
        for(int i = 0 ; i < graph[here].size() ; i++){
            PIL there = graph[here][i];
            if(!visited[there.first]){
                visited[there.first] = true;
                cost[there.first] = cost[here] + there.second; // update
                if(max_cost < cost[there.first]){ // update max-node, cost
                    max_cost = cost[there.first];
                    max_node = there.first;
                }
                Q.push(there.first); // push node
            }
        }
    } // 1-BFS : search start node
 
    Q.push(max_node);
    max_cost = -1;
    cost = VLL(n+1,0);
    visited = VB(n+1, false);
    visited[max_node] = true;
    while(!Q.empty()){
        int here = Q.front(); Q.pop();
        for(int i = 0 ; i < graph[here].size() ; i++){
            PIL there = graph[here][i];
            if(!visited[there.first]){
                visited[there.first] = true;
                cost[there.first] = cost[here] + there.second; // update
                if(max_cost < cost[there.first]){ // update max-cost
                    max_cost = cost[there.first];
                }
                Q.push(there.first); // push node
            }
        }
    } // 2-BFS : result cost
 
    printf("%lld\n",max_cost);
 
    return 0;
}