알고리즘 문제 해결 전략 2 06장 트리 (2)

21.5 문제 요새

성벽들의 정보가 주어질 때 임의의 두 지점 간을 이동하기 위해 최대 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하시오.

 

21.6 풀이: 요새

성벽들은 서로 닿거나 겹치지 않는다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있음. 따라서 성벽들 간의 포함 관계를 트리로 나타내서 문제를 풀어낼 수 있음. 이렇게 트리를 구성하고 나면, 한 구역에서 인접한 다른 구역으로 가기 위해 성벽을 넘는 일은 이 트리에서 간선을 따라 다른 노드로 옮겨가는 것으로 대응됨. 따라서 두 지점을 왕래하기 위해 성벽을 가장 많이 넘어야 하는 경우를 찾는 문제는 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제가 됨.

 

트리에서 가장 긴 경로 찾기

이와 같은 모델링 과정을 거치면 이 문제는 주어진 트리에서 가장 긴 경로를 구하는 문제로 바뀜. 다행히 트리에서 최장 경로를 구하는 문제는 어렵지 않게 풀 수 있음. 최장 경로 문제를 푸는 열쇠는 최장 경로의 양 끝 노드가 항상 루트 혹은 잎 노드여야 함을 깨닫는 것임. 최장 경로의 길이는 다음 줄 더 큰 값이 됨.

1. 가장 긴 루트-잎 경로의 길이

2. 가장 긴 잎-잎 경로의 길이

height()는 지금까지 찾은 가장 긴 경로의 길이를 저장하는 전역 변수 longest를 갱신하는 방식으로 동작함. 

struct TreeNode{
	vector<TreeNode*> children;
};

int longest;
int height(TreeNode* root) {
	vector<int> heights;
	for (int i = 0; i < root->children.size(); ++i)
		heights.push_back(height(root->children[i]));
	if (heights.empty()) return 0;
	sort(heights.begin(), heights.end());
	if (heights.size() >= 2)
		longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);
	return heights.back() + 1;
}

int solve(TreeNode* root) {
	longest = 0;
	int h = height(root);
	return max(longest, h);
}

height()로 트리 전체를 처리하는 데는얼마의 시간이 걸리까요? 서브트리들의 높이를 정렬하는 데 드는 O(nlgn)의 시간을 무시하면 트리의 순회와 다를바가 없으므로, O(n)의 시간이 걸림. 

 

실제 구현

입력으로부터 트리를 생성하는 과정과 생성한 트리에서의 최장 경로를 구하는 부분으로 나눌 수 있음. isChild() 함수는 O(n) 시간에 수행되는데, 트리 생성 과정에서 각 노드를 방문할 때마다 n번 isChild()를 호출하기 때문에 전체 트리 생성 과정의 시간 복잡도는 O(n^3)이 됨. 미리 성벽들을 크기 순서대로 정렬해 두면, 트리 생성 과정을 엔제곱에 수행할 수 있음.