[BOJ/백준][Gold4] 1967: 트리의 지름 (C++)

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

 

[난이도] Gold4

[유형] 트리의 지름(DFS)

 

[풀이] 

트리의 지름 : 트리에서 거리가 가장 먼 두 점 사이의 거리. 구

하는 방법 : 임의의 점에서 DFS로 가장 먼 점을 찾은 뒤에 그 점에서 DFS를 이용해서 가장 먼 점을 찾으면 그 거리가 트리의 지름이 된다.

 

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,ans,mxN,mxV;
bool visit[10001];
vector<pair<int,int>> adj[10001];
void dfs(int n,int c){
    visit[n] = 1;
    if(c>mxV){
        mxV=c;
        mxN=n;
    }
    for(auto nxt : adj[n]){
        if(!visit[nxt.first]) dfs(nxt.first,c+nxt.second);
    }
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1,0);
    memset(visit,0,sizeof(visit));
    mxV=0;
    dfs(mxN,0);
    printf("%d",mxV);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1967.cpp