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

 

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

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

#define MAX 10001
using namespace std;

vector<pair<int, int>>v[MAX];
bool visited[10001] = {false};
int ans = 0;
int endpoint = 0;

void dfs(int num, int length){
    if(visited[num]){
        return;
    }

    visited[num] = true;

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

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

int main(){

    int N;
    int a;
    int b;
    int c;
    cin>>N;

    for(int i = 0; i < N-1; i++){
        cin>>a>>b>>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }

    dfs(1, 0);
    ans = 0;
    memset(visited, false, sizeof(visited));
    dfs(endpoint, 0);

    cout<<ans<<endl;

    

    return 0;
}​

 

 

앞서 블로그에 올린 백준 1167번 트리의 지름과 결이 같은 문제이다. 문제를 풀 수 있다면

1167번도 풀 수 있을 것이다.

해당 문제 링크 : https://www.acmicpc.net/problem/1167

 

 

 

dfs를 이용한 문제이다.

dfs에서 length와 endpoint를 설정해둔다.

if(ans < length){

ans = length;

endpoint = num;

}으로 계속해서 갱신해서 길이가 최대일 때의 끝 점을 저장한다.

 

b>c>a

루트노드에서 DFS를 실행하게되면 3방향으로 뻗어나가는데

결국에는 길이 값이 제일 큰 b길이 쪽으로 엔드 포인트가 저장이된다.

 

저장된 엔드포인트를 다시 dfs를 실행해준다.

 

두번째로 큰 C길이의 엔드포인트가 3으로 찍히게 되며

length가 b+c로 갱신되면서 트리의 지름을 구할 수 있게 된다.