백준 1167, 1967 - 트리의 지름

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

1167번: 트리의 지름

두 문제가 입력방식만 다르고 문제 내용은 똑같다. 또한 1167번이 값의 범위가 더 커서 1167번을 먼저 풀면 1967번은 날먹이 가능해진다.

 

0. 처음 떠올린 아이디어는 다음과 같다. 모든 점에서 DFS를 실시한다. DFS에서, 벽에 막혀서 되돌아갈 때 그 때까지 이동한 거리를 확인해 최대값을 저장한다. 점마다 구한 최대값을 비교해 가장 큰 값을 출력한다.

 

이렇게 해도 답은 구할 수 있겠지만, 모든 점에서 DFS를 수행해야 하므로 시간이 오래 걸린다. DFS는 일반적으로 O(|E|)번 수행되며 트리 구조에서 |E| = |V| - 1이므로, 전체 시간복잡도는 O(|V|^2) 정도일 것이다.

 

1. 과연 꼭 모든 점에서 DFS를 수행해야 할까? 지름이란 양 끝점을 이은 선분을 말한다. 그렇다면 유일한(?) 지름이 존재할 때, 그 선분의 양 끝에 있는 점 중 하나만 찾아도 되지 않을까? 그 점만 찾는다면 1번의 DFS로 지름의 길이를 구할 수 있을 것이다. 예제의 그래프에서는 1, 5번 노드가 그 끝점에 해당하겠다.

 

2. 그렇다면 끝점을 어떻게 찾아야 하는가? 당연히 나는 모르고, 구글링을 해보니 아무 점이나 골라 DFS를 수행했을 때 시작점과의 거리가 가장 먼 점이 트리의 지름을 이루는 점이라고 한다.

예제 1번에서도, 각 노드에 대해 최대 거리를 갖게 하는 끝점을 구해보면 모두 5가 나온다.

 

3. 이제 두번의 DFS를 통해 손쉽게(나한텐 안 쉬움) 트리 지름의 길이를 찾을 수 있다.

코드

//현재 위치, 시작점부터의 거리
void DFS(int node, int dist) {
	visited[node] = 1;

	//최장거리가 갱신될 때마다 정보 저장
	if (diameter < dist) {
		diameter = dist;
		tail = node;
	}

	PII next;
	for (auto next : graph[node]) {
		if (!visited[next.first]) {
			DFS(next.first, dist + next.second);
		}
	}

}

void solve() {
	//임의의 점에서 DFS 수행
	DFS(1, 0);
	
    //다음 DFS 전 변수와 배열 초기화
	fill(visited.begin(), visited.end(), 0);
	diameter = 0;
	
    //지름의 끝점에서 다시 DFS 수행
	DFS(tail, 0);
	cout << diameter << endl;
}

 

느낀 점

구현이 익숙하지 않으면 아이디어를 덧붙이기 전에 해당 알고리즘의 기본형부터 떠올려보자