백준 1167 c++ - [PlusUltraCode]

[필자 사고]

 

트리의 지름을 구하라는 문제이다. 먼저 트리의 지름이란 임의이 두 점을 골랐을 때 가장 거리가 긴 길이가 트리의 지름이다.

먼저 임의이 아무 지점에서 각 지점에서의 최단 거리를 구한다. 

최단거리중 거리가 가장 긴 IDX를 골라 시작점으로 다시 최단 거리를 구하게 되면 가장 거리가 긴 지점이 나오게 된다.

 

 

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

using namespace std;

typedef pair<int, int> Node;
const int MAX_NUM = 10000000;
vector<vector<Node>> Arr;
vector<bool> visited;
vector<int> pathLoad;
int N;
priority_queue<Node> pq;
void Input() {
	cin >> N;
	Arr.resize(N + 1);
	pathLoad.resize(N + 1, 10000000);
	visited.resize(N + 1, false);

	for (int i = 0; i < N; i++) {
		int start;
		cin >> start;
		while (1) {
			int end, weight;
			cin >> end;
			if (end == -1)break;
			cin >> weight;
			Arr[start].push_back({ weight,end });
		}
	}
}

void Init() {
	pathLoad.clear();
	visited.clear();
	pathLoad.resize(N + 1, 10000000);
	visited.resize(N + 1, false);
}


void Solve() {
	pq.push({ 0,1 });
	pathLoad[1] = 0;
	while (!pq.empty()) {
		Node nowNode = pq.top();
		int nowIdx = nowNode.second;
		int nowWeight = nowNode.first;
		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 });
			}
		}
	}
	int findIdx = -1;
	int findMax = -1;
	for (int i = 0; i <= N ; i++) {
		if (pathLoad[i] == MAX_NUM)continue;
		if (findMax < pathLoad[i]) {
			findMax = pathLoad[i];
			findIdx = i;
		}
	}
	Init(); //방문한곳과 pathLoad초기화 진행
	pq.push({ 0,findIdx });
	pathLoad[findIdx] = 0;
	while (!pq.empty()) {
		Node nowNode = pq.top();
		int nowIdx = nowNode.second;
		int nowWeight = nowNode.first;
		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 });
			}
		}
	}
	findIdx = -1;
	findMax = -1;
	for (int i = 0; i <= N; i++) {
		if (pathLoad[i] == MAX_NUM)continue;
		if (findMax < pathLoad[i]) {
			findMax = pathLoad[i];
			findIdx = i;
		}
	}
	cout << findMax;
}
int main(void) {
	Input();
	Solve();
}