백준 1167번 트리의 지름

문제 이해

처음에는 트리와 그래프를 혼동했던 것 같다. 그래서 아래와 같은 상황이 발생할 수 있다고 생각하여 트리의 모든 경로를 검사하는 코드를 짰더니 시간 초과가 발생했다. 

 

그런데 트리는 그래프와는 다르게 여러 노드가 한 노드를 가리킬 수 없다 (위키백과).

 

그러므로 이 문제의 경우

1. 한 노드에서부터 탐색을 하며 가장 먼 노드를 찾은 뒤,
2. 다시 그 노드부터 탐색을 하며 가장 먼 거리를 찾으면 된다. (참고)

 

증명

트리의 지름은 언제나 리프노드 사이에서 존재한다.

임의의 노드에서 가장 먼 리프 노드를 먼저 찾은 후, 그 리프 노드에서 가장 먼 리프노드까지의 거리가 트리의 지름이다.

 

아래와 같은 트리가 있다고 하자.

탐색의 시작 노드를 4번으로 했을 때, 가장 먼 리프 노드는 7번이고 거리는 11이다.

다시 7번부터 탐색을 시작하면, 가장 먼 리프 노드는 5번이고 거리는 19인데, 이것이 바로 트리의 지름이다.

트리를 다른 관점에서 보면 다음과 같다.

첫 번째 탐색에서 찾은 경로는 주황색, 두 번째 탐색에서 찾은 경로(트리의 지름)는 빨간색 형광펜으로 표시하였다. 트리의 지름인 빨간색 경로는 첫 번째 탐색에서 찾았던 주황색 경로의 일부를 포함하는 것을 볼 수 있다.

 

첫 번째 탐색에서는 1번 갈림길에서 7번 노드까지의 경로를 선택했다. 1번 갈림길에서 갈 수 있는 모든 길 중 7번까지의 경로가 가장 길기 때문이다. 다시 7번부터 탐색을 시작하면, 다시 1번 갈림길에서 갈 수 있는 모든 길 중 최장거리인 5번까지의 경로를 선택한다. 1번 노드를 중심으로 양쪽으로 가장 긴 경로를 선택했기 때문에 그것이 트리의 지름이 되는 것이다. 중심은 탐색을 어떤 노드에서부터 시작하느냐에 따라 바뀔 수 있다. 예를 들어 6번 노드에서 탐색을 시작했다면 3번 노드가 중심이 될 것이다. 

 

구현

탐색은 DFS를 사용하였고, 트리는 list를 사용해서 구현하였다.

// 1167 트리의 지름

#pragma warning(disable: 4996)

#include <iostream>
#include <list>
using namespace std;

#define MAX 100000 + 1

int V;	// no. of nodes in a tree
list<pair<int, int>> tree[MAX];
bool visited[MAX] = { 0 };	// using when traversing
int maxNode;	// be the start node of second traversal
int maxWght = 0;	// maximum sum of weight in the path

void DFS(int node, int weight) {
	if (visited[node]) {
		return;
	}

	visited[node] = true;

	if (weight > maxWght) {
		maxWght = weight;
		maxNode = node;
	}

	list<pair<int, int>>::iterator it;
	for (it = tree[node].begin(); it != tree[node].end(); ++it) {
		DFS(it->first, weight + it->second);
	}
}

int main() {
	scanf("%d", &V);

	// build a tree
	for (int i = 0; i < V; i++) {
		int node1;
		scanf("%d", &node1);

		while (true) {
			int node2;
			scanf("%d", &node2);

			if (node2 == -1) {
				break;
			}

			int weight;
			scanf("%d", &weight);

			tree[node1].push_back(make_pair(node2, weight));
		}
	}

	// find the longest path in the tree
	DFS(1, 0);

	// set values of visited array to 0
	for (int i = 0; i <= V; i++) {
		visited[i] = 0;
	}

	// second traversal
	DFS(maxNode, 0);

	// print the answer
	printf("%d", maxWght);

	return 0;
}

 

문제 링크: www.acmicpc.net/problem/1167