[백준/BOJ] 1167 트리의 지름 - 접근과 풀이 (c++)

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

1167번: 트리의 지름

그래프만 다루다보니 트리가 잊혀져가서 트리문제중 기억에 남던 문제를 다시 풀어보았다.

 

---

접근 방법

 

1967번과 같은 문제인데, 노드의 갯수가 늘어났다. V가 최대 10만이므로, O(n^2)의 방법으로는 풀리지 않음을 주의해야한다

아무 노드를 루트로 지정하여, 아래로 내려갈 때 가장 긴 길이와 두번째로 긴 길이를 구하여 더하는 방식으로 접근했다.

그러나 위의 그림1 처럼, 루트가 아님에도 지름인 경우가 존재하므로, 자식을 탐색하면서 모든 노드에 대해 가장 긴 길이와 두번째로 긴 길이를 구하여 전역변수로 저장한 ans 변수에 가장 긴 길이를 갱신해준다. 

 

위 풀이는 모든 노드에서 해당 노드를 지나는 가장 긴 길이를 O(V+간선갯수) 만에 구한다.

 

자식에서 가장 긴 길이를 구하는 방법은 노드에서 재귀로 넘겨주면 되므로 어렵지 않다. 

 

---

풀이

 

tag : dfs, tree

#include<iostream>
#include<vector>
#include<utility>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int V;
int ans=-1;
vector<pii> adj[100011];
int solve(int v,int parent){ //v반노드 순회하고, 가장 긴 길이 반환
  int maxLength=0; //가장긴
  int max2Length=0;//그다음긴
  for(int i=0;i<adj[v].size();i++){
    int child=adj[v][i].first;
    int weight=adj[v][i].second;
    if(child == parent) 
      continue;
    int calcLength=weight+solve(child,v);
    if(calcLength>maxLength){// 가장기네
      max2Length=maxLength;
      maxLength=calcLength;
    }
    else if(calcLength>max2Length){ //두번째로기네
      max2Length=calcLength;
    }
    
  }
  ans=max(ans,maxLength+max2Length);
  return maxLength;
}
int main(){
  cin>>V;
  for(int i=0;i<V;i++){
    int vnum;
    int v,w; //노드,가중치
    cin>>vnum;
    while(1){
      cin>>v;
      if(v==-1)
        break;
      cin>>w;
      adj[vnum].push_back(mp(v,w));
    }
  }

  solve(1,-1);
  cout<<ans;
}

문제를 풀기 전에 엄청 참신한 풀이가 있었던 것 같은데 기억이 안났다. 그래도 나만의 방법으로 문제를 풀어서 뿌듯했다.

그 풀이는 아무 노드를 루트로 하여 가장 깊은 곳에 있는 노드를 구한 후, 해당 노드에 대하여 가장 깊은 길이를 구하는 것이다. 대박~