[ 백준 ] 1967번 - 트리의 지름 ( C++ )

dfs를 이용하여 푸는 문제이다.

풀이를 생각해보는데 쉽게 떠오르지 않았다.

고민 끝에 다른사람의 풀이를 참고하였다.

 

<문제>

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

1967번: 트리의 지름

 

 

<참고해서 푼 풀이>

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> node[10002];
bool visited[10002] = {false,};
int result = 0;
int endPoint = 0;

void dfs(int p, int len){
  if(visited[p]) return;
  
  visited[p] = true;
  if(result < len){
    result = len;
    endPoint = p;
  }
  
  for(int i=0; i<node[p].size(); i++){
    dfs(node[p][i].first, len + node[p][i].second);
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int n;
  cin>>n;
  
  for(int i=0; i<n-1; i++){
    int a,b,c;
    cin>>a>>b>>c;
    node[a].push_back({b,c});
    node[b].push_back({a,c});
  }
  
  dfs(1,0);  //가장 멀리있는 점 구하기
  
  result = 0;
  memset(visited, false, sizeof(visited));
  
  dfs(endPoint, 0);  //지름 구하기
  cout<<result;
}

 

원의 내부에서 가장 끝 점에 있는 두 지점이 지름에 해당하기 때문에

어떤 정점에서 출발을 해도 가장 멀리 있는 지점은 원의 지름에 해당하는 두 정점중에 하나일 것이다.

 

그래서 어떤 한 정점에서 dfs를 수행하여 가장 멀리 있는 지점을 찾은 후에

그 지점에서 다시 dfs를 수행해 가장 멀리 있는 지점과의 거리 즉, 지름을 구하면 된다.

 

위 논리를 생각한다면 어렵지 않게 풀었을 문제인데 생각하지 못했다.