(백준 c++)1167 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

 

dfs를 2번 해주도록 한다.

임의의 정점에서 가장 멀리 있는 정점(end_point)을 구한다.

그리고 end_point에서 가장 멀리 있는 정점을 구하면 트리의 지름이 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<pair<int, int>> tree[100001];
vector<bool> visited(100001, false);
int answer = 0;
int V = 0;
int end_point = 0;

void dfs(int start, int sum){
    if(visited[start]){
        return;
    }

    visited[start] = true;

    if(answer < sum){
        answer = sum;
        end_point = start;
    }

    for(int i = 0; i < tree[start].size(); i++){
        dfs(tree[start][i].first, sum + tree[start][i].second);
    }
}

int main(void){
    cin >> V;

    //트리 만들기
    for(int i = 0; i < V; i++){
        int N, tmp, target = 0, dist = 0;

        cin >> N;

        while(1){
            cin >> target;
            
            if(target == -1){
                break;
            }
            cin >> dist;
            tree[N].push_back(make_pair(target, dist));
        }    
    }

    //임의의 정점에서 가장 멀리 있는 정점 구하기
    dfs(1, 0);
    answer = 0;
    
    //방문 여부 초기화
    for(int i = 1; i <= V; i++){
        visited[i] = false;
    }

    //end_point와 가장 멀리 있는 정점 구하기
    dfs(end_point, 0);
    
    cout << answer << endl;
    return 0;
}