백준 1967 트리의 지름

1. 문제 링크

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

2.  풀이

 

위 사진처럼 자식 노드부터 순차적으로 탐색해 나가면서 부모 노드로 올라갈 때에는 최댓값 2개를 골라 더해준 후 정답 값보다 크면 정답 값을 업데이트해 준다.

그러고 나서 리턴 값으로는 자식에서 올라온 값 중 가장 큰 값을 리턴해 준다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Element {
public:
	int vertex, weight;
	Element() {};
	Element(int vertex, int weight) {
		this->vertex = vertex;
		this->weight = weight;
	};

};

int n;
vector<Element> graph[10001];
bool visited[10001];

void InputAndInit() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		graph[i].clear();
		visited[i] = false;
	}

	int start, end, weight;
	for (int i = 0; i < n - 1; i++) {
		cin >> start >> end >> weight;
		graph[start].push_back({ end,weight });
		graph[end].push_back({ start,weight });
	}
}

int Reculsive(int c_root, int& c_max, const int prevWeight) {
	vector<int> c_vec;
	visited[c_root] = true;

	for (Element child : graph[c_root]) {
		if (!visited[child.vertex])
			c_vec.push_back(Reculsive(child.vertex, c_max, child.weight));
	}
	if (c_vec.size() == 0)
		return prevWeight;
	else if (c_vec.size() == 1) {
		c_max = c_max > c_vec[0] ? c_max : c_vec[0];
		return c_vec[0] + prevWeight;
	}
	else {
		sort(c_vec.begin(), c_vec.end(),greater<int>());
		c_max = c_max > c_vec[0] + c_vec[1] ? c_max : c_vec[0] + c_vec[1];
		return c_vec[0] + prevWeight;
	}
}

int GetResult() {
	int res = 0;
	Reculsive(1, res, 0);
	return res;
}

int main() {
	InputAndInit();
	cout << GetResult() << "\n";
}