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;
}

참고 자료