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

접근 

해당 문제를 풀기 위해서는

• 트리와 그래프의 차이점
• 트리에서 임의의 노드 i 를 잡아 가장 먼 거리에 위치한 노드 j 를 찾았을 때 j로부터 가장 길이가 먼 노드 k를 찾음으로 트리의 지름을 구할 수 있음

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

이해했다면 총 두 번의 탐색을 통해 트리의 지름을 구할 수 있음을 알 수 있습니다. (두 번의 탐색을 통해 트리의 지름을 구할 수 있다는 말을 이해하고 동의해야 합니다)

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

 

풀이 과정 

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

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

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

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

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

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

 

솔루션 

주의 
입력받는 노드의 번호가 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;
}

 

참고 자료 

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

https://www.acmicpc.net/board/view/83695

https://www.acmicpc.net/source/29046625

[자료구조] 그래프와 트리(Graph, Tree)