[C++] 백준 1967 트리의 지름

트리의 기본적인 개념을 잡고 난 후에 풀 수 있는 문제다. 트리(Tree)란 사이클이 없는 그래프라고 본문에서 나온다.

고로 dfs로 해결이 가능했다. 최댓값을 찾은 후에 최댓값을 갱신 해주면서 가장 멀리 있는 정점을 찾고 최댓값을 초기화

해준 후 다시 dfs를 돌려서 최댓값을 찾아주는 알고리즘을 짰다.

#include <bits/stdc++.h>
#define MAX 10001
using namespace std;

struct Pair {
	int fir, sec;
};

vector<Pair> v[MAX];
bool visited[MAX] = {false};
int Max = 0, End = 0; //최댓값, 끝지점 변수

void dfs(int a, int l) {
	if (visited[a]) return;
	
	visited[a] = true;
	if (Max < l) //보다 더 큰 최댓값을 발견했다면 
		Max = l, End = a;
	
	for (int i = 0; i < (int)v[a].size(); i++)
		dfs(v[a][i].fir, l + v[a][i].sec);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;

	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}

	dfs(1, 0); //1부터 시작해서 가장 멀리 있는 노드 구하기

	Max = 0; 
	memset(visited, false, sizeof(visited)); //초기화

	dfs(End, 0);
	cout << Max;
}