[백준 1967번] [트리] 트리의 지름

이 문제의 경우에는 사실 트리보다는 DFS를 활용하는 것에 가깝다.

처음에 접근한 방법은 루트 노드를 바탕으로 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾아나가는 방법이다.

하지만, 잘 생각해보면 루트 노드가 고정되어 있는 것처럼 표현하지만 어떠한 노드를 잡아도 루트화 시킬 수 있다.(적절하게 변형하면 된다.)

 

즉, 모든 노드에 대하여 재귀를 통해 DFS처리하면서 가중치 최댓값들을 찾고, 그 중 최댓값을 출력해주면 된다.

해당하는 내용을 토대로 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct node{
    vector<pair<int, int> > path_store;
};

int checker(node *data_store, int start, int len){
    int sum = len;

    int length = data_store[start].path_store.size();
    int max = 0;
    for(int i = 0 ; i < length; i++){
        if(max < checker(data_store, data_store[start].path_store[i].first, data_store[start].path_store[i].second)){
            max = checker(data_store, data_store[start].path_store[i].first, data_store[start].path_store[i].second);
        }
    }
    sum += max;

    return sum;
}

int main(void){
    int n;
    cin >> n;

    node data_store[n + 1];

    for(int i = 0; i < n - 1; i++){
        int parent, child, length;
        cin >> parent >> child >> length;
        data_store[parent].path_store.push_back(make_pair(child, length));
    }// data_store

    int max = 0;

    for(int i = 1; i < n + 1; i++){
        int data_size = data_store[i].path_store.size();
        vector<int> sum_store(10001,0);
        for(int j = 0; j < data_size; j++){
            sum_store[j] = checker(data_store, data_store[i].path_store[j].first, data_store[i].path_store[j].second);

        }
        sort(sum_store.begin(), sum_store.end(), greater<int>());
        if(max < sum_store[0] +sum_store[1] ) max = sum_store[0] +sum_store[1];
    }

    cout << max << "\n";

    return 0;
}

 해당 코드에 대한 결과는 다음과 같다.

시간 제한이 2초인 것에 비하여 생각보다는 여유롭게 통과한 편인데, Time complexity를 대략적으로 고려해보자면 다음과 같다.

41번째 for loop 안에 sort가 있으므로 O(n^2lgn)이라는 것을 확인할 수 있다.

즉, 통과는 하였지만 매우 비효율적인 방법이라는 것을 알 수 있다.

관련하여 검색하던 중, 위 문제를 풀기위한 최적의 알고리즘이 존재한다는 것을 알게 되었다.

1. 트리에서 임의의 정점 x를 잡는다. (이 문제에서는 루트 노드를 선택하면 된다.
2. 정점 x에서 가장 먼 점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.

트리의 지름은 정점 y와 정점 z를 연결하는 경로이다. 

증명 방법은 꽤 복잡한 편이니 넘어가도록 하자. 

직관적으로 보면 되게 당연한데, 한 정점을 기준으로 양끝으로 뻗어나가면서 최대가 되는 지점들은 잡은 상황이다.

하지만, 그 정점을 지나지 않고 최대가 되는 지점에 대해서는 검토하지 않은 상황이므로 그것을 따로 판단해주면 되는 것이다.

 

위의 내용을 코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

struct node{
    vector<pair<int, int> > path_store;
};

//방문체크
int visited[10001] = {0};
//끝점체크
int end_point = 0;
//지름길이
int answer = 0;

void dfs(node *data_store, int start, int length){
    if(visited[start] != 0) return;
    else{
        visited[start] = 1;
        //거리보다 크다면 저장(아래에 노드가 없는 경우도 커버가능)
        if(answer < length){
            end_point = start;
            answer = length;
        }
        for(int i = 0; i < data_store[start].path_store.size(); i++){
            dfs(data_store, data_store[start].path_store[i].first, length + data_store[start].path_store[i].second);
        }
        return;
    }
}

int main(void){
    int n;
    cin >> n;

    node data_store[n + 1];

    for(int i = 0; i < n - 1; i++){
        int parent, child, length;
        cin >> parent >> child >> length;
        data_store[parent].path_store.push_back(make_pair(child, length));
        data_store[child].path_store.push_back(make_pair(parent, length));
    }// data_store

    // 끝점 찾기
    dfs(data_store, 1, 0);

    //방문기록 초기화
    fill_n(visited, 10001, 0);

    // 최종 거리 찾기
    dfs(data_store, end_point, 0);

    cout << answer << "\n";

    return 0;
}

해당 코드에 대한 결과는 다음과 같다.

위의 코드로 했을 때보다 확실히 빠르다는 것을 알 수 있다.

위 코드의 time complexity는 O(n)으로 앞의 코드보다 훨씬 효율적으로 처리할 수 있다.

 

트리의 지름을 구하는 방법에 대해서 잘 정리해두도록 하자.