백준 1167 트리의 지름

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int n;
class TreeNode {
public:
	int data;
	vector<pair<int, int>> connections; //{node, dist}
	TreeNode() {
		data = 0;
	}
	TreeNode(int data) : data(data) {}
};

class Tree {
public:
	TreeNode head;
	int size;
	Tree(TreeNode head, int size) : head(head), size(size) {}
};


int bfsSearch(int size, int startNodeNum, int& maxDistEndNode, vector<TreeNode*>& treenodeVector) {
	queue<int> bfsSearchQueue;
	vector<int> distVector_FromStart(size + 1, 0);
	vector<bool> isVisit(size + 1, false);
	int maxDistFromStart = 0;
	bfsSearchQueue.push(startNodeNum);
	isVisit[startNodeNum] = true;
	int nowNode;
	while (!bfsSearchQueue.empty()) {
		nowNode = bfsSearchQueue.front();
		int dist_StartToNow = distVector_FromStart[nowNode];
		for (auto it = treenodeVector[nowNode]->connections.begin(); it < treenodeVector[nowNode]->connections.end(); it++) {
			auto nextNodePair = *it;

			if (isVisit[nextNodePair.first] == false) {

				int distFromNode_1ToNextNode = dist_StartToNow + nextNodePair.second;
				distVector_FromStart[nextNodePair.first] = distFromNode_1ToNextNode;

				if (distFromNode_1ToNextNode > maxDistFromStart) {
					maxDistFromStart = distFromNode_1ToNextNode;
					maxDistEndNode = nextNodePair.first;
				}
				bfsSearchQueue.push(nextNodePair.first);
				isVisit[nextNodePair.first] = true;
			}
		}
		bfsSearchQueue.pop();
	}
	return maxDistFromStart;
}

int main() {
	int size;
	scanf("%d", &size);
	vector<TreeNode*> treenodeVector;

	treenodeVector.push_back(new TreeNode(0));
	for (int i = 1; i <= size; i++) {
		treenodeVector.push_back(new TreeNode(i));
	}

	for (int i = 1; i <= size; i++) {
		int input_nodeNum;
		scanf("%d", &input_nodeNum);
		while (true) {
			int input_connectNode;
			scanf("%d", &input_connectNode);
			if (input_connectNode == -1) break;
			int input_nodeDist;
			scanf("%d", &input_nodeDist);
			treenodeVector[input_nodeNum]->connections.push_back(make_pair(input_connectNode, input_nodeDist));
		}
	}

	int maxDistNodeFromNode_1 = 0;
	int maxDistFromNode_1 = 0;
	vector<int> distFromNode_1(size + 1 , 0);

	queue<int> bfsFromNode_1;
	bfsFromNode_1.push(1);
	maxDistFromNode_1 = bfsSearch(size, 1, maxDistNodeFromNode_1, treenodeVector);
	int endNode;
	int result = bfsSearch(size, maxDistNodeFromNode_1, endNode, treenodeVector);
	printf("%d\n", result);
	return 0;
}

트리의 지름을 구하는 방법은 아래와 같다

1. 임의의 점에서부터 가장 먼 거리의 점을 구한다.

2. 1에서 구한 점에서부터 가장 먼 거리의 점과의 거리를 구한다.

3. 2에서 구한 거리가 지름

'1에서 구한 점이 지름에 속하지 않는 점이다' 가 모순임을 보이면 쉽게 증명이 가능하다.