백준 1167(트리의 지름)

 

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

1967번: 트리의 지름

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다.

 

처음에는 모든 노드에 대해서 루트로 잡은 노드와 가장 먼 노드와의 길이를 dfs를 통해 구해보았다. 

당연하게도 시간초과가 발생하였다.

 

한번의 DFS 로 풀 수 있는 방법이 있을까 고민해보았다.

 

생각의 흐름.

 

1. 내가 현재 루트로 잡은 노드가 트리의 지름에 포함되어있는 경우

-> 이 경우 루트 노드부터 한 리프 노드까지가 트리의 지름일 수 도 있고, 아니면 한 리프 노드부터 루트 노드를 지나 다른 리프 노드까지가 지름일 수 있다.

 

2. 내가 현재 루트로 잡은 노드가 트리의 지름에 포함되어있지 않을 경우

그림이 허접하지만 빨간색 노드가 루트 노드이고 파란 부분이 트리의 지름이다.

위 그림같은 경우를 말할 수 있다.

 

여기까지 생각해보니  하나의 노드에서 두가지를 처리해주면 위에서 정리한 두가지 경우를 모두 처리할 수 있을 것 같았다.

 

첫번째, 자식 노드는 부모에게 자신부터 리프노드까지의 길이 중 최대값을 반환해준다.

두번째, 부모 노드는 자식 노드들 중에서 가장 긴 두개의 노드 길이의 합을 구해 answer와 비교한다.

 

위의 설명으로 알아들을 사람은 없을 것 같다.. 설명을 더 잘할 수 있도록 노력해야겠다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int>>vec[100001];

bool check[100001];

int ans = 0;
int dfs(int now){
    int first=0;
    int second =0;
    for(int i=0; i<vec[now].size(); i++){
        if(check[vec[now][i].first] ==false){
            check[vec[now][i].first]=true;
            int temp = dfs(vec[now][i].first) + vec[now][i].second;
            if(first < temp || second < temp ){
                if(first <= second)first = temp;
                else second = temp;
            }
        }
        
    }
    if(ans < first + second)ans =first + second;
    return max(first,second);
}

int main(){
    int n;
    scanf("%d",&n);
    
    int st,fi,score;
    for(int i=0; i<n; i++){
        scanf("%d",&st);
        while(1){
            scanf("%d",&fi);
            if(fi != -1){
                scanf("%d",&score);
                vec[st].push_back(make_pair(fi,score));
            }
            else break;
        }
    }
    check[1] = true;
    dfs(1);
    printf("%d",ans);
    
    return 0;
}

근데 왜 DFS 한번 쓴 내 풀이가 기존 풀이보다 속도가 느린것일까..

대부분 80ms 에서 끝내는데 내 코드는 108ms 걸린다...

 

문제를 푼 뒤 다른 풀이를 찾아보니 DFS 두번 적용하여 푸는 방법도 있었다.

설명으로 보나  코드로 보나 내 풀이보다 깔끔한 것 같다.