백준 1967 트리의 지름

#define _CRT_SECURE_NO_WARNINGS

//#define _FILE_INPUT_

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <fstream>

using namespace std;

class TreeNode {
public:
	int num;
	vector<pair<int, int>> connections; //node, dist
	int maxDist_first = 0;
	int maxDist_second = 0;
	TreeNode() {
		num = 0;
	}
	TreeNode(int num) : num(num) {}
	void pushSonDist(int dist) {
		if (dist > maxDist_second) {
			maxDist_second = dist;
			if (dist > maxDist_first) {
				maxDist_first = maxDist_first + maxDist_second;
				maxDist_second = maxDist_first - maxDist_second;
				maxDist_first = maxDist_first - maxDist_second;
			}
		}
	}
	int getMaxDist() {
		return maxDist_first + maxDist_second;
	}
};


vector<TreeNode*> nodeVtr;
int _size;

void fileInput() {
	ifstream inFile("input.txt");
	inFile >> _size;
	for (int i = 0; i <= _size; i++) {
		nodeVtr.push_back(new TreeNode(i));
	}
	int parent = 0, son = 0, dist = 0;
	for (int i = 2; i <= _size; i++) {
		inFile >> parent >> son >> dist;
		nodeVtr[parent]->connections.push_back(make_pair(son, dist));
		//nodeVtr[son]->connections.push_back(make_pair(parent, dist));
	}
}
void consoleInput() {
	scanf("%d", &_size);
	for (int i = 0; i <= _size; i++) {
		nodeVtr.push_back(new TreeNode(i));
	}
	int parent = 0, son = 0, dist = 0;
	for (int i = 2; i <= _size; i++) {
		scanf("%d %d %d", &parent, &son, &dist);
		nodeVtr[parent]->connections.push_back(make_pair(son, dist));
		//nodeVtr[son]->connections.push_back(make_pair(parent, dist));
	}
}

int calc_maxDist(int node) {
	auto sons = nodeVtr[node]->connections;
	if (nodeVtr[node]->maxDist_first > 0) {
		return nodeVtr[node]->maxDist_first;
	}
	if (sons.size() <= 0) {
		return 0;
	}
	else if (sons.size() == 1) {
		nodeVtr[node]->pushSonDist(calc_maxDist(sons[0].first) + sons[0].second);
		return calc_maxDist(sons[0].first) + sons[0].second;;
	}
	else {
		int max_result = 0;
		for (auto it = sons.begin(); it < sons.end(); it++) {
			nodeVtr[node]->pushSonDist(calc_maxDist(it->first) + it->second);
			max_result = max(max_result, calc_maxDist(it->first) + it->second);
		}
		return max_result;
	}
}

int main() {
#ifdef _FILE_INPUT_
	fileInput();
#else 
	consoleInput();
#endif

	int maxDist = calc_maxDist(1);

	queue<int> bfsSearchQueue;
	bfsSearchQueue.push(1);
	while (!bfsSearchQueue.empty()) {
		int nowNode = bfsSearchQueue.front();
		auto nowNodePtr = nodeVtr[nowNode];
		maxDist = max(maxDist, nodeVtr[nowNode]->getMaxDist());
		bfsSearchQueue.pop();
		for (auto it = nowNodePtr->connections.begin(); it < nowNodePtr->connections.end(); it++) {
			bfsSearchQueue.push(it->first);
		}
	}
	printf("%d\n", maxDist);

	return 0;
}

예전에 다른 비슷한 문제를 풀었는데 (http://deque.tistory.com/33 , 백준 1167 트리의 지름)

그때는 루트가 주어지지 않았다.

그래서 그 문제를 풀 때는 루트를 굳이 찾지 않고, 

임의의 점에서 가장 먼 점을 찾고

그 점에서 가장 먼 점을 찾아서 그 거리를 계산했다.

그런데 이번엔 루트가 1이라고 문제에 박아놨으니까

다르게 한번 풀어보기로 했다.

방법은 이렇다

1. 재귀를 이용하여 BFS방식으로 접근하면서, 각 노드에 연결된 잎사귀들 중 제일 먼 거리와 그 다음으로 먼 거리를 각 노드에 저장한다.

2. 만약 노드의 자식이 1개인 노드에 접근 하면, (그 다음으로 먼 거리)는 0으로 둔다.

3. 이번에는 반복문으로 BFS방식으로 접근하면서 각 노드에서 방금 저장한 (제일 먼 거리, 그 다음으로 먼 거리) 의 합을 구한다

4. 3에서 구한 값들의 최대값이 지름이 된다.

근거는 다음과 같다.

트리의 지름이란

A. 잎사귀 -> 잎사귀

B. 머리 -> 잎사귀

이런 두가지 경우의 최대값이다.

A에 해당하는건 일자형 트리가 해당 될 수 있겠고, B에 해당하는건 일반적인 2진트리 같은 것들이 해당 될 수 있겠다.

A의 경우든 B의 경우든, 각 노드에 저장된 (제일 먼 거리, 그 다음으로 먼 거리)의 합을 구하면 

각 노드가 루트일 경우의 지름을 구할 수 있다.

일종의 DP처럼 푼것 같은데

점화식으로 나타내면

i = [1...n] 일경우에

DP(n) = max(

DP(n->son[0]) + dist(n, n->son[0])

, DP(n->son[1]) + dist(n, n->son[1])

, DP(n->son[2]) + dist(n, n->son[2])

...

, n->son[m]

)                        :   n->son[k]는 n의 k번째 자식,

dist(a, b)는 a노드와 b노드의 거리,

DP(n)은 node[n] 과 가장 먼 잎사귀까지의 거리

이고, 부가적으로 DP(n)을 계산하면서 최대값 뿐만 아니라, 차대값도 node[n]에 저장한다.

왜냐하면 우리가 구해야 할 (잎사귀->잎사귀)는 (잎사귀->머리 + 머리->잎사귀)이고, 이 값은 (DP를 계산하며 저장한 최대값 + 차대값)이기 때문이다.

DP(n)으로 나온 결과는 지름이 아니고, node[n]에서 가장 먼 잎사귀까지의 거리이다.

따라서 정답을 구하려면 다시 한번 모든 노드를 순회하면서 방금 저장한 최대값과 차대값의 합의 최대값을 구해야 한다.

부가적으로 B에 해당하는 경우가 지름일 경우에도 위와 같이 계산하면 자연스럽게 계산이 되는데,

왜냐하면 B의 경우가 지름일 경우에는 자식이 하나인 경우일테고, 이때는 위에서 계산한 차대값이 무조건 0이 되기 때문이다(거리가 양수이기 때문).

그렇기 때문에, 모든 노드를 순회하며 정답을 구할 때, 자연스럽게 '최대값' + '차대값'(=0) = '최대값' 이 될 것이고, 이 최대값은

'잎사귀->머리'의 값이기 때문이다!

하 말로 설명하려니 힘든데,

결론적으로

각 노드에 대해 잎사귀까지의 거리를 구하고,

그 거리중 가장 먼거리와 그 다음으로 먼 거리의 합중 최대값이 지름이다

라는 것..

그 와중에 머리->잎사귀인 경우가 지름이 되는 경우도 고려하기 위해 각 노드의 '가장 먼 거리'와 '그 다음으로 먼 거리'를 0으로 미리 초기화 해놓는다

정도..