BOJ 1967

트리의 지름 성공

 

 

2 초

128 MB

29437

11906

9017

42.228%

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

입력

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력 1 복사

12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10

45

트리문제이다.

처음에 시간계산할떄 N^2logE면 풀릴줄 알고 그냥 다익스트라 비슷하게 만들어서 박았는데 안풀렸다.

왜인지 다시 계산해보니 

1. 1초가 걸리는 경우가 10^9 로 알고있었는데, 다시 찾아보니 10^8 정도였다. 이러면 N^2이 넘어가는 연산은 절대 풀릴 수 없다.

 

2. 잘 짠  다익스트라에선 pq를 사용하여 NlogE를 만드는데, 위의 문제는 최단거리가 아닌 최장거리 이므로 결국 모든 노드, 모든 간선을 방문하게 된다. 출발지가 정해져 있는 다익스트라는 N개의 노드를 모두 탐색해 주어야 하고, 알고리즘 자체가 N * N-1의 시간이 걸리니 N^3 이라는 말도 안되는 시간이 걸리게 된다.

 

그러므로 원래의 코드대로는 풀 수 없었다.

 

그러므로 시작점은 1 로 고정되어 있으니, 제일 거리가 먼 지점 하나를 구하여 총 두번의 탐색을 돌릴 수 있게 하였다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;
int N, ans;
vector<vector<pair<int,int>>>tree(10001);
pair<int,int> dy(int id){
    vector<int>dist(10001, -1);
    dist[id] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>>pq;
    int vis[10001]={0};
    pq.push({0,id});
    vis[id] = 1;
    while(!pq.empty()){
        int cur_node = pq.top().second;
        int cur_dist = pq.top().first;
        pq.pop();
        for(auto edge : tree[cur_node]){
            int nxt_node = edge.first;
            int nxt_dist = cur_dist + edge.second;
            if(vis[nxt_node])  continue;
            if(nxt_dist > dist[nxt_node]){
                dist[nxt_node] = nxt_dist;
                pq.push({nxt_dist,nxt_node});
                vis[nxt_node] = 1;
            }
        }
    }
    int idx=1, idxc = 0;
    for(int i=1; i<=N; i++){
        if(dist[i] == -1) continue;
        if(dist[i] > dist[idx])
            idx = i; 
        idxc = max(idxc, dist[i]);
    }
    // for(int i=1; i<=N; i++)
    //     cout<<dist[i]<<' ';
    // cout<<endl;
    return {idx,idxc};
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>N;
    for(int i=0; i<N-1; i++){
        int a, b, c;
        cin>>a>>b>>c;
        tree[a].push_back({b,c});
        tree[b].push_back({a,c});
    }
    auto ver = dy(1);
    cout<<dy(ver.first).second;
}

처음 풀이를 최대한 살려서 코드가 더럽고, 시간도 간당간당하게 되었다.

그냥 DFS로 짜면 이것보다 훨씬 간결해진다.