백준 1967 - 트리의 지름(C++)

문제

사이클이 없는 무방향 그래프 트리(tree)가 주어질 때 트리의 지름을 구하는 문제다.

 

입력

첫째 줄에 노드의 개수 N (1 <= N <= 10,000)가 입력된다.

 

둘째 줄 부터 N - 1개의 줄에 각 간선에 대한 정보가 입력된다.

 

예제 입력

12
1 2 3
1 3 2
2 4 5
3 5 11
3 6 9
4 7 1
4 8 7
5 9 15
5 10 4
6 11 6
6 12 10

 

예제 출력

45

 

문제 해결

 

어디서 힌트를 얻을 수 있을까?

 

'그래프', '트리', '트리의 지름'이라는 키워드를 본 순간 이 문제는 트리의 지름을 구하는 이론을 이용해서 문제를 풀면 된다는 것을 알 수 있었다.

 

그리고 '간선의 가중치'를 보고 이 문제는 DFS를 이용해야 한다는 것도 눈치챌 수 있었다.

 

코드

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>

typedef std::pair<int, int> P;

std::vector<P > varr[10001];
int maxNode, maxDis;
int cache[10001];

void dfs(int S, int dis)
{
	if (cache[S] != 0)
		return;
	cache[S] = 1;
	if (maxDis < dis)
	{
		maxNode = S;
		maxDis = dis;
	}
	for (int i = 0; i < varr[S].size(); i++)
		dfs(varr[S][i].first, varr[S][i].second + dis);
}

int main(void)
{
	int N;
	std::cin >> N;
	int X, Y, C;
	int ret;
	while (1)
	{
		if (!(std::cin >> X >> Y >> C))
			break ;
		varr[X].push_back(P(Y, C));
		varr[Y].push_back(P(X, C));
	}
	dfs(1, 0);
	std::memset(cache, 0, sizeof(cache));
	maxDis = 0;
	dfs(maxNode, 0);
	std::cout << maxDis << std::endl;
	return 0;
}

 

문제 출처

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

1967번: 트리의 지름

 

이론

https://deulee.tistory.com/8

트리의 지름 증명