[백준]Baekjoon1967 (트리의 지름)

문제 링크 : https://www.acmicpc.net/problem/1967

트리의 지름을 구하기 위해서는 먼저 기준점을 잡아야되는데

기준점을 잡기위해 루트로부터 가장 길이가 긴 점을 선택한다.

기준점을 잡은 후 기준점으로부터 트리를 탐색하면서 거리의 최댓값을 구하면

답을 구할 수 있다.

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

#define SIZE 10001

using namespace std;

typedef struct __NODE
{
	int next = -1;
	int cost = -1;
}node; //다음 노드와 가중치 저장

vector<node> v[SIZE];
bool check[SIZE];
pair<int, int> p = make_pair(0,0);

void function(int start,int distance)
{
	check[start] = true; //탐색한 노드는 체크
	for (int i = 0; i < v[start].size(); i++) {
		if (!check[v[start][i].next]) { //연결된 노드를 탐색한적이 없다면
			function(v[start][i].next, distance + v[start][i].cost); //cost를 더하면서 다음 노드 탐색
		}
		else {
			if (distance > p.first) { //연결된 노드를 탐색한적이 있고
				// 그 노드까지의 거리가 지금까지 저장한 길이의 최댓값보다 크다면
				p.first = distance;
				p.second = start;
			}
		}
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	int x, y, cost;

	for (int i = 0; i < n - 1; i++) {
		cin >> x >> y >> cost;
		node n;
		n.next = y; n.cost = cost;
		v[x].push_back(n);
		n.next = x;
		v[y].push_back(n);
	}

	function(1, 0); //루트에서 제일 먼 노드 찾기
	memset(check, false, n + 1); //check 초기화

	function(p.second, 0); //찾은 노드에서 가장 먼 노드 찾기 
	printf("%d\n", p.first); //distance 반환
}