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