백준 1167, 트리의 지름(C, C++)

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

1167번: 트리의 지름

#include<iostream>
#include<vector>
#include<string.h>

using namespace std;

vector<pair<int, int>> a[100001];

int visited[100001];
int ans = 0;
int endpoint;

void dfs(int start, int length){

    if(visited[start] == true){
        return;
    }

    if(ans < length){
        ans = length;
        endpoint = start;
    }

    visited[start] = true;

    for(int i = 0; i < a[start].size(); i++){
        int next = a[start][i].first;
        int cost = a[start][i].second;
        if(!visited[next]){
            dfs(next, cost + length);
        }
    }
}

int main(){
    int V;
    int x;
    int y;
    int w;
    cin>> V;
    for(int i = 0; i < V; i++){
        cin >> x;
        while(1){
            cin>>y;
            if(y == -1){
                break;
            }
            cin>>w;
            a[x].push_back({y, w});
            a[y].push_back({x, w});
            }
    }
    dfs(1, 0);
    ans = 0;
    memset(visited, false, sizeof(visited));
    dfs(endpoint, 0);

    cout<<ans;
    
    return 0;

}

DFS를 이용한 문제이다.

예시로 1부터 9의 노드가 존재하는 트리가 있다고 생각합니다.

여기서 1부터 시작하는 DFS를 사용했을 경우

간선을 이용하여 값을 비교하며 최댓값과 지나는 노드를 저장, 갱신합니다.

결국에는 

1->2->4->9의  최대 길이를 가지는 경로를 지납니다.

9번 노드에서 DFS가 종료되며, Endpoint와 최댓값이 저장됩니다.

저장된 Endpoint를 우리가 만든 DFS함수에 대입하게되면 다시 한 번 최대 길이를 찾게 되는데

 

9 - 4 - 2 - 1 - 3 - 6 를 지나면서 값과 지나는 노드들 비교하며 갱신하여  최대 길이 8과  endpoint = 6을 저장합니다.