Skip to main content

백준 1167 트리의 지름 C++ 문제 풀이

풀이​

해당 문제를 풀기 위해서는

들을 반드시 이해해야 합니다.

이해했다면 총 두 번의 탐색을 통해 트리의 지름을 구할 수 있음을 알 수 있습니다.

대부분 인터넷에서 찾을 수 있는 풀이는 dfs로 풀지만 전 다익스트라를 통해 풀어보겠습니다.

탐색하는 그래프가 트리임이 보장되므로, 절대 사이클을 가지지 않습니다.

사이클을 가지지 않으므로 최소 거리 == 해당 노드로 가는 거리 입니다.

해당 노드로 가는 최장 거리와 최소 거리는 동일합니다.

따라서 가장 기본적인 다익스트라 탐색 형태를 적용하더라도 해당 노드로 가는 거리를 구할 수 있습니다.

첫 번째 다익스트라 탐색을 통해 노드 0 으로부터 가장 먼 노드 node 를 구합니다.

두 번째 다익스트라 탐색을 통해 노드 node 으로부터 가장 먼 노드와의 거리를 구합니다.

접근​

솔루션​

warning

입력받는 노드의 번호가 1부터 시작함을 인지하고 문제를 푸세요!

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int N;
int node = 0;
int dist = 0;
// [from] <to, dist>
vector < pair <int, int> > GRAPH[100001];

void dijkstra(int start) {
    // <dist, node>
    priority_queue < pair<int, int>, vector < pair< int, int > >, greater< pair <int, int > > > PQ;
    vector <int> DIST(100001, 2e9);

    PQ.push(make_pair(0, start));
    DIST[start] = 0;

    while(!PQ.empty()){
        int w = PQ.top().first;
        int cur = PQ.top().second;

        PQ.pop();

        for(int i=0; i<GRAPH[cur].size(); i++){
            int wNext = GRAPH[cur][i].second;
            int curNext = GRAPH[cur][i].first;

            if(DIST[curNext] > w + wNext) {
                DIST[curNext] = w + wNext;
                PQ.push(make_pair(w + wNext, curNext));
            }
        }
    }

    // 해당 노드로부터 가장 먼 노드와 그 길이 계산
    node = 0;
    for(int i=0; i<N; i++){
        if(dist < DIST[i]) {
            node = i;
            dist = DIST[i];
        }
    }

    return;
}

int main(){
    // 입력
    cin >> N;
    for(int n=0; n<N; n++){
        int from, to, dist;
        cin >> from >> to;
        while(to != -1){
            cin >> dist;

            GRAPH[from-1].push_back(make_pair(to-1, dist));
            GRAPH[to-1].push_back(make_pair(from-1, dist));

            cin >> to;
        }
    }

    // 계산
    dijkstra(0);
    dijkstra(node);

    cout << dist;

    return 0;
}

참고 자료​