[IOI2011 Day1] Race 해법

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/race.pdf

이 문제는 분할정복기법(Divide & Conquer)로 풀 수 있다. 노드 v를 선택하고 v를 포함한 길이가 K인 경로 중 가장 짧은 경로를 찾는다. 그리고 노드 v를 제거한다. 남은 트리들에서 일련의 과정을 반복한다. 분할정복으로 풀기 위해서는 다음 두 사항을 해결해야된다.

• 어떻게 노드 v를 포함한 가장 좋은 경로를 찾을 수 있는가?
• 수행시간을 최적으로 만들 노드 v를 어떻게 찾아야 하는가?

우선 노드 v를 포함한 가장 좋은 경로를 찾는 법은 꽤 간단하다. 노드 v를 루트로 한 트리를 만들고 dfs를 돌리면 길이가 K이면서 가장 짧은 경로를 O(N)만에 찾을 수 있다. dfs를 돌릴 때 크기가 K인 배열을 이용해야한다.

어떤 노드 v를 선택하고 v를 제외하면 새로운 트리들이 만들어진다. 각 새로운 트리들에서 일련의 과정을 다시 거쳐야한다. 위 알고리즘의 시간복잡도가 O(N)이다. 따라서 단계가 지남에 따라 트리의 노드 개수가 많이 줄어들어야 총 수행시간이 작아진다. 따라서 노드 v를 어떻게 선택하느냐가 총 수행 시간을 결정한다.

노드의 개수가 N인 트리 T에서 다음 조건을 만족하는 노드 v는 항상 존재한다: 노드 v를 제외하고 새로운 트리들을 만들었을 때 새로운 트리들의 노드 개수는 N/2이하이다.

위 조건을 만족하는 v를 찾으면 된다. 나름의 증명과 함께 노드 v를 구하는 방법을 설명하겠다. root에서 부터 시작하면서 자기 자식들의 서브트리의 노드 개수가 N/2 보다 크면 그 노드로 이동하고 이를 계속 반복한다. 그러면 마지막 노드는 위의 조건을 만족한다. 이 방법이 가능한 이유는 다음과 같다.

• 현재 노드가 root 일 때, 자기 자식 노드들 중 서브트리의 노드 개수가 N/2 보다 큰 것이 없다면 현재 노드는 조건을 만족한다.
• 현재 노드가 root가 아니라는 것은 트리 T에서 자신의 서브트리를 제외한 트리의 노드 개수가 N/2 보다 작다는 것이다. 따라서 현재 노드가 root가 아닐 때, 자기 자식 노드들 중 서브트리의 노드 개수가 N/2 보다 큰 것이 없다면 현재 노드는 조건을 만족한다.
• 이 재귀 함수는 트리에서 깊이가 깊어지는 방향으로만 들어가므로, 절대 무한 루프에 빠져들지 않는다. 즉, 함수가 항상 어떤 노드에서 멈춤이 보장된다.

이 알고리즘의 총 시간복잡도를 구하겠다.

$T(N) = O(N) + \sum{T(N_i)}$ 여기서 $(N_i \leq \frac{N}{2})$

따라서 총 시간복잡도는 $O(N lg N)$ 이다.

코드: http://ideone.com/Sqnj8l