[백준,c++] 1167번 - 트리의 지름

문제

1167번: 트리의 지름

 

코드

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;
vector<pair<int,int>> graph[100001];

int max_len = 0, max_node;
bool visited[100001];

void find_max_len(int node, int len){
    visited[node] = true;
    if(len>max_len){
        max_node = node;
        max_len = len;
    }
    
    for(auto next: graph[node]){
        if(!visited[next.first]){
            visited[next.first] = true;
            find_max_len(next.first, len + next.second);
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int V; cin>>V;
    
    for(int i=0; i<V; i++){
        int node_a = 0, node_b, cost;
        for(int k=0;; k++){
            if(k==0) cin>>node_a>>node_b>>cost;
            else{
                cin>>node_b;
                if(node_b == -1) break;
                cin>>cost;
            }
            graph[node_a].push_back({node_b, cost});
        }
    }
    
    find_max_len(1, 0);
    memset(visited, 0 ,sizeof(visited));
    max_len = 0;
    find_max_len(max_node, 0);
    
    
    cout<<max_len;
}

 

풀이

[백준,c++] 1967번 - 트리의 지름

유명한 문제입니다. 이전에 풀었던 위 문제와 거의 동일합니다.

이 문제는 시간 초과에 유의해야 하는데 저는 처음에 아래와 같이 모든 노드들을 탐색하면서 가장 긴 지름을 찾았습니다.

for(int i=1; i<=V; i++){
	find_max_len(i, 0);
	memset(visited, 0 ,sizeof(visited));
}

하지만 당연하게도 해당 코드는 O(100,000 ^ 100,000)으로 시간 초과가 발생합니다. 

고민했던 부분은 과연 어떻게 가장 긴 노드를 바로 찾을 수 있을까 인데, 사실 이 부분은 딱 한 번만 아무 노드나 잡고 가장 멀리 있는 노드를 찾으면 됩니다.

입출력의 트리 그림

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

위와 같은 입출력에서 어느 노드(1, 2, 3 ,4, 5)를 잡고 시작해도 1 혹은 5로 나오게 됩니다.

따라서 1이 나왔다면 1에서 가장 멀리 있는 노드(5)까지의 거리를 구하고, 5가 나왔다면 5에서 가장 멀리있는 노드(1)까지의 거리를 구하면 됩니다.

따라서 시간복잡도 O(100,000 + 100,000)만에 구할 수 있습니다.