BOJ - 1967번 트리의 지름 (C++)

문제 출처: https://www.acmicpc.net/problem/1967

문제 난이도

Gold 5

문제 접근법

처음엔, 루트 노드인 1부터 시작해 깊이 탐색으로 좌 우 판단 후 합한 길이가 제일 길 때를 구했다. -> 틀림
그래서 두번째, 1부터 시작해 제일 긴 길이를 가진 노드를 구하고 그 노드에서 또 제일 긴 길이를 구한다. 그럼 그 긴 길이를 가진 노드에서 시작한 제일 긴 길이는 답이 된다.
즉, dfs를 두번 돌린다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

#define INF 987654321

using namespace std;

vector<pair<int,int>> t[10002];
bool ch[10002];
int n,ans,endNode;

void dfs(int node,int len) {
	if (ch[node]) return;
	ch[node] = true;
	if (ans < len) {
		ans = len;
		endNode = node;
	}
	for (int i = 0; i < t[node].size(); i++) {
		dfs(t[node][i].first, len + t[node][i].second);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		t[a].push_back({ b,c });
		t[b].push_back({ a,c });
	}
	dfs(1, 0);
	ans = 0;
	memset(ch, false, sizeof(ch));
	dfs(endNode, 0);
	cout << ans << "\n";
	return 0;
}