[BOJ] 1167 트리의 지름 C++

 

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

1167번: 트리의 지름

이 문제를 대충 요약하자면 트리에서 정점->정점까지 가장 긴 거리를 구하는 것이다. 

내가 이 문제를 보고 무조건 시작 또는 끝에는 트리의 리프노드일 것을 알았다. 그래서 모든 리프노드(연결 된 노드가 하나밖에 없는 노드)를 구해서 dfs를 각각 돌려 그 중 최댓값을 구하면 되겠다고 생각했는데 바로 시간초과가 떴다.

고민을 하다가 다른 분의 코딩을 참조 했는데 알고리즘은 다음과 같다.

1. 임의의 점을 루트노드로 잡고 거리가 최대인 리프노드를 구한다.

2. 리프노드를 로트노드로 잡고 최대 거리를 구하면 이것이 트리의 지름이다.

처음 이걸 보고 한참 생각했다. 친구가 설명을 해줬는데도 바로 와닿지 않아서 밑에 블로그를 보고 한참 생각하다 깨달았다.

https://blog.myungwoo.kr/112

트리의 지름 구하기

(블로그를 참조 할때 d(t,y)=max(d(t,u),d(t,v))부분을 d(t,y)>=max(d(t,u),d(t,v))로 바꿔줘야한다.)

트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하고 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y를 찾았을 때, u,v,x,y가 모두 다른 경우의 수는 존재하지 않는다.(반드시 y가 u,v이거나 x가 u,v여야 한다.)

 

코드

#include <iostream>
#include <vector>
using namespace std;

bool check[100001];
vector<pair<int,int> > v[100001];
vector<int> end_node;
int max_idx,max_dist=0;
int N;
void dfs(int start,int dist_sum){
    check[start]=true;
    bool flag=false;
    int size=v[start].size();
    for(int i=0;i<size;i++){
        int go=v[start][i].first;
        int dist=v[start][i].second;
        if(!check[go]){
            dfs(go,dist_sum+dist);
            flag=true;
        }
    }
    check[start]=false;
    if(flag) return;
    if(max_dist<dist_sum){
        max_idx=start;
        max_dist=dist_sum;
    }
}
int main(){
    int start;
    cin>>N;
    for(int i=1;i<=N;i++){
        int from;
        cin>>from;
        while(1){
            int to,dist;
            cin>>to;
            if(to==-1) break;
            cin>>dist;
            v[from].push_back(make_pair(to,dist));
        }
        if(v[from].size()==1) start=from;
    }
    int ans=0;
    dfs(1,0);//임의의 점
    dfs(max_idx,0); //최대값을 갖는 인덱스에서 dfs
    cout<<max_dist;
    return 0;
}