Subways (POI 2006)

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

증명에 증명을 더해가면서 시간 복잡도를 줄이는 스타일의 그리디였는데 재밌었다. 일단 먼저 N^2 알고리즘을 목표로 시작해보자. 가장 많은 역을 덮는 지하철 노선의 집합을 최적 집합이라고 한다.

Lemma 1. 최적 집합의 모든 끝점을 리프로 변형시킬 수 있다.

증명 : 그렇지 않은 최적 집합이 존재한다면 이를 두고 생각해 보자. 만약에 현재 끝점이 리프가 아니면, degree가 2 이상이라 빠져나갈 구멍이 하나 존재한다. 이 구멍으로 경로의 길이를 증가시켜나가면 답을 감소시키지 않으면서 한쪽을 리프로 만들어 줄 수 있다. 

Lemma 2. 최적 집합에 덮인 지하철역이 서브트리를 이루게 변형시킬 수 있다. (이 때 서브트리는 subgraph로써의 뜻을 가진다)

증명 : 최적 집합의 모든 끝점이 리프로 변형된 상황에서, 리프를 dfs preorder 순으로 정렬하자. 2K개의 리프가 있다면 L[0] - L[K], L[1] - L[K+1] 을 이어주는 식으로 모든 간선을 만들어 준다. L[i] - L[i + K] 을 잇는 간선과 L[i + 1] - L[i + K + 1]을 잇는 간선이 교차함을 보일 수 있다. 고로 이들은 연결되어 있고 서브트리를 이룬다.

이제, O(N^2) 알고리즘을 찾을 수 있다. 서브트리는 최소 하나의 리프를 포함할테니, 이 리프를 고정시키고 시작해보자. 리프를 루트로 한 트리를 생각해 보자. 이 rooted tree에서 2K-1개의 또다른 리프를 고를 것이고, 이들이 서브트리를 이루니까. 결국 루트에서 2K-1개의 리프를 적당히 골라서 선택된 정점을 최대화해야 한다. 이는 KOI 2013 수족관 3에서 사용하는 것과 비슷한 그리디를 사용할 수 있는데, 자세한 설명은 생략한다. 정렬을 통해서 O(NlgN)에 해결할 수 있는 그리디이지만 제한이 작아서 count를 관리하는 것만으로도 O(N) 시간 복잡도를 만들 수 있다. 이를 모든 리프에 대해서 시도하니 O(N^2) 알고리즘이 나온다.

현재의 알고리즘을 최적화하는 데는 다음 Lemma가 도움이 된다.

Lemma 3. 최적 집합이 임의의 지름을 포함하게 변형시킬 수 있다.

증명 : 만약 최적 집합과 지름의 교집합이 없다고 하자. 최적 집합에서 하나의 지하철 노선을 제거해도 지름의 개수 이하의 지하철역만 덮을 수 없다. 지름을 추가하면 지름의 길이만큼의 지하철역이 덮여진다. 고로 답을 감소시키지 않으면서 지름을 추가할 수 있다.

교집합이 있다고 하자. 서브트리와 경로의 교집합이기 때문에 교집합은 경로를 이룬다. 이 경로에서 지름의 양 끝점에 가장 가까운 점을 L, R이라고 하자. L에서 다른 리프로 나가는 임의의 간선을 골라서, 해당 방향의 지름으로 보내버린다. R에서도 마찬가지로 한다. 이 과정에서 만약에 답이 감소했다면, 더 큰 단순 경로가 존재한다는 것을 뜻한다. 이는 처음에 지름을 잡았다는 가정에 모순이다.

고로, 우리가 구하고자 하는 서브트리는 임의의 지름의 양 끝점을 항상 포함한다. 한쪽 끝점을 포함하는 최적 집합만 찾아도. 답을 찾을 수 있다는 뜻이다. 고로 모든 리프를 볼 필요가 없어져서 O(N) 시간 복잡도가 나온다.