백준 1967 c++ -[PlusUltraCode]

[필자 사고]

트리의 지름문제이다. 

 

처음보면 당황할 수 있지만 한번만 이해하면 쉽게 풀 수 있는 문제이다.

트리의 지름이란 임의의 두점을 선택했을때 가장 거리가 긴 노드간의 길이를 말한다.

지름을 구하기 위해서는 다음과 같다.

 

1. 임의의 노드 하나를 선택하여 가장 거리가 먼 노드를 구한다.

2. 가장 거리가 먼 노드에서 다시 시작하여 가장 거리가 먼 노드를 또 구한다.

3. 2번째로 구한 가장 거리가 먼 노드의 길이가 지름의 길이이다.

 

문제를 해결하는 알고리즘은 dfs 다익스트라 등등 많이 있고 필자는 다익스트라를 이용하여 해결했다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> Node;

vector<vector<Node>> Arr;
vector<bool> visited;
vector<int> pathLoad;
int N;

void djistra(int start) {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,start });
	pathLoad[start] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		pq.pop();
		if (visited[nowIdx] == true)continue;
		visited[nowIdx] = true;
		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextWeight = nextNode.first;
			if (visited[nextIdx] == false &&
				pathLoad[nextIdx] > pathLoad[nowIdx] + nextWeight) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextWeight;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}

}

void Init() {
	visited.clear();
	pathLoad.clear();

	visited.resize(N + 1, false);
	pathLoad.resize(N + 1, INT_MAX);
}

void Input() {
	cin >> N;
	Arr.resize(N + 1);
	Init();
	for (int i = 1; i < N; i++) {
		int start, end, weight;
		cin >> start >> end >> weight;
		Arr[start].push_back({ weight,end });
		Arr[end].push_back({ weight,start });
	}

}

void Solve() {
	
	djistra(1);

	int findIdx = -1;
	int findMax = -1;
	for (int i = 0; i <= N; i++) {
		if (pathLoad[i] == INT_MAX)continue;
		if (findMax < pathLoad[i]) {
			findMax = pathLoad[i];
			findIdx = i;
		}
	}

	Init(); //방문 및 pathLoad 초기화
	
	djistra(findIdx);

	findMax = -1;
	for (int i = 0; i <= N; i++) {
		if (pathLoad[i] == INT_MAX)continue;
		if (findMax < pathLoad[i]) {
			findMax = pathLoad[i];
		}
	}
	cout << findMax;

}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Solve();
}