BOJ 1967 트리의 지름

문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다.

문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드에서 가장 깊이 들어가야 최소한 최대 길이가 될것 같다는 생각을 하였다. DFS를 생각한것이다.

 

하지만 DFS 한번만으로 도저히 답을 찾아낼 수 없었다. 풀이를 보니 DFS를 두번 사용 해야 한다고 하였다.

 

왜 DFS를 두번 사용해야 하는지 이해가 안되다가 다음과 같은 특징을 이해한 다음에 문제를 해결할 수 있었다.

하나의 정점에서 가장 멀리 있는 정점은 원의 지름 부분에 해당하는 정점이다.

 

즉 어느 점에서 DFS를 통해 가장 긴 점을 찾으면 그 점은 가장 지름이 긴 원의 시작 점이 된다. 이후 그 시작점에서 또 가장 긴 점을 찾으면 결국 그 점까지의 길이가 최대 지름이 된다.

 

이 방법을 스스로 떠오르기가 너무 힘든거 같다. 다음에 비슷한 문제가 나오면 빠르게 풀수 있을것 같다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<functional>
using namespace std;

int n;
pair<int, int> maxNode = { 0,0 };
bool visited[100001];
vector<pair<int,int>> node[100001];

void DFS(int parent, int w,int totalWeight)
{
	visited[parent] = true;

	for(int i = 0; i < node[parent].size(); i++)
	{
		int child = node[parent][i].first;
		int weight = node[parent][i].second;
		if(!visited[child])
		{
			DFS(child, weight, (totalWeight + weight));
		}
	}

	int nodeNum = maxNode.first;
	int maxTotal = maxNode.second;
	if(maxTotal < totalWeight)
	{
		maxNode = { parent,totalWeight };
	}
	return;
}

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

	memset(node, 0, sizeof(node));
	memset(visited, false, sizeof(visited));

	cin >> n;
	for(int i = 0; i < n-1; i++)
	{
		int p, c, w;
		cin >> p >> c >> w;
		node[p].push_back({ c,w });
		node[c].push_back({ p,w });
	}

	DFS(1, 0, 0);
	
	int startNode = maxNode.first;
	memset(visited, false, sizeof(visited));
	maxNode = { 0,0 };

	DFS(startNode, 0, 0);

	cout << maxNode.second;
}