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

문제 설명

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리를 구하는 프로그램을 작성해라.

입력

트리가 입력으로 주어진다.

 

첫 번째 줄에는 정점의 개수 V가 주어진다. (2 <= V <= 100,000)

 

그 다음 줄에는 정점의 번호가 주어지고 연결된 간선의 정보를 의미하는 정수 두 개씩 주어진다.

 

하나는 정점의 번호, 다른 하나는 연결된 정점 까지의 거리가 주어진다.

 

예제 입력

5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1

출력

11

문제 해결

어떻게 힌트를 얻을 수 있을까?

 

우선 키워드를 통해 문제를 대충 유추할 수 있었다. 정점과 간선이라는 단어를 통해 해당 문제는 그래프 이론을 이용해서 풀 수 있겠다라는 것을 유추할 수 있었다.

 

그리고 트리의 지름이란 곧 최적화 문제를 의미하는 것이기도 하다.

 

그리고 주어진 목적지 및 최소의 문제가 아니었기 때문에 BFS(너비 우선 탐색) 보다 DFS(깊이 우선 탐색)가 더 유용할 거라고 생각했다.

이 전에 해결한 적이 있는가?

 

DFS를 구현하는 것은 이전에도 해보았기 때문에 방법을 떠올리면 금방 할 수 있었다.

 

시간 복잡도

이 문제의 시간 복잡도는 DFS를 이용하기 때문에 한 번의 DFS에서 사용되는 N번의 반복문과 모든 정점 N을 돌아야 하므로, 시간 복잡도는 다음과 같다.

 

O(N^2)

 

오류

맨 처음에 각 정점에서 전부 다 실행해서 가장 큰 지름을 구하려고 했었다. 이렇게 되면 O(N^3)이라는 시간 복잡도를 가지게 되어서 시간 초과할 것을 전혀 생각하지 못했다.

 

이를 해결하기 위해 고민을 해본 결과 다음의 궁금증을 가질 수 있게 되었다.

 

트리의 지름을 구하는 이론이 따로 존재하지 않을까? 라는 궁금증을 가질 수 있게 되었다. 이러한 궁금즘은 역시나 맞았고 이는 다음의 내용과 같았다.

 

1. 임의의 정점 x 하나를 정해서 먼저 DFS를 시행한다.

2. 임의의 정점 x 에서 가장 먼 정점 y를 구한다.

3. y에서 DFS를 시행하여 y에서 가장 먼 정점 z를 구한다.

 

검증은 다음 글 혹은 아래 글을 참고하자.

코드

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

struct Node {
	int idx;
	int dis;
};

std::vector<Node> varr[100001];
int cache[100001];
int maxNode;
int maxDis;

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

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int V;
	std::cin >> V;
	for (int i = 0; i < V; i++)
	{
		int node;
		std::cin >> node;
		int x, y;
		while (1)
		{
			std::cin >> x;
			if (x == -1)
				break ;
			std::cin >> y;
			varr[node].push_back({x, y});
		}
	}
	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/1167

1167번: 트리의 지름

이론

https://deulee.tistory.com/8

트리의 지름 증명