골드4 - 백준 1967 트리의 지름

백준 1967 트리의 지름

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

접근방법

트리의 지름을 구하는 방법은 임의의 노드에서 가장 먼곳에 있는 노드를 구하고 그 노드에서 다시 가장 멀리 있는 노드까지의 거리를 구하면 된다.

풀이

노드 1에서 가장 거리가 먼 노드를 구하기 위해 dfs 함수를 이용하였다. dfs 함수는 더이상 자식 노드가 없다는 것을 flag를 통해서 확인하고 리프 노드라면 sum 변수에 저장된 거리값을 Max와 비교해주어 갱신해주었다. 갱신시에 가장 먼 노드를 구하기 위해서 temp_node에 저장하였다.
그리고 visited와 Max를 초기화하고 다시 한번 dfs를 실행시켜서 temp_node부터 가장 먼 노드까지 거리를 Max에 저장하여 출력해주었다.

코드

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

using namespace std;

vector<pair<int, int>> route[10001];
int Max = 0;
int temp_node;
bool visited[10001];

void dfs(int node, int sum)
{
	bool flag = true;
	for (int i = 0; i < route[node].size(); i++)
	{
		if (visited[route[node][i].first])
			continue;

		flag = false;
		visited[route[node][i].first] = true;
		dfs(route[node][i].first, sum + route[node][i].second);
	}

	if (flag)
	{
		if (Max < sum)
		{
			Max = sum;
			temp_node = node;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N - 1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		route[a].push_back({ b,c });
		route[b].push_back({ a,c });
	}

	visited[1] = true;
	dfs(1, 0);
	memset(visited, false, sizeof(visited));
	Max = 0;

	visited[temp_node] = true;
	dfs(temp_node, 0);

	cout << Max << endl;
}