Greedy on Tree

Sun Jan 07 2024

트리는 아주 특수한 그래프의 일종이고, 상당히 강력한 성질들이 많이 존재한다. 또한 subtree 내부와 외부가 상호작용하는 정도가 작다는 성질 때문에 다양한 object의 최적해들을 greedily 구할 수 있는 경우가 많이 존재한다. 이 글에서는 기록을 목적으로 몇 가지 문제들에 대한 내 증명을 적어둔다.

Diameter of Tree

트리의 지름을 구하는 문제는, 가장 떨어진 거리가 먼 두 정점 쌍을 찾는 문제이다. 임의의 정점 $i$에서 가장 멀리 떨어진 정점을 $a$라고 하자. $a$에서 가장 멀리 떨어진 정점을 $b$라고 하면, $(a, b)$가 지름을 이루는 두 정점이라는 것이 claim이다. 트리의 아무 지름 $(c, d)$를 잡고, $c$에서 $d$로 가는 경로 위에 놓인 정점들이 순서대로 $u_1, \ldots, u_k$라고 하자. 그러면 전체 트리는 $c$에서 $d$로 가는 정점들과, $u_i$를 루트로 하는 subtree들로 구성된 꼴이 된다. $c$와 $d$는 항상 차수가 $1$인 정점인 것도 확인할 수 있다. 또한 이런 경우, $u_t$의 subtree는 $u_t$의 깊이를 $0$으로 볼 때 기껏해야 $min(t, k+1-t)$의 깊이를 가지게 된다. 그게 아니라면 $u_t$ 내부에서 가장 깊은 깊이의 정점을 잡으면, $c$나 $d$와 연결했을 때 둘 중 하나가 $(c, d)$의 거리보다 길다.

그러므로 위에서 설명한 greedy 과정에서 $i$가 $u_t$의 subtree에 있는 정점이라고 하자. WLOG $t < \frac{k+1}{2}$라고 하면, $a$에 해당하는 점은 $d$가 되거나, $d(i, a) = d(i, d)$를 최소한 만족한다. 그런데 $a \neq d$인 경우 어찌 됐건 $(c, a)$도 지름을 이루는 정점일 수밖에 없다. 그러면 항상 greedy 과정에서 잡히는 $a$는 반드시 어떠한 지름을 구성하는 정점 쌍에 포함될 수 있는 정점이라는 뜻이므로, 항상 $b$가 $(a, b)$가 되도록 잡히게 된다.

주유소 (KOI 2023)

트리가 주어질 때 정점들의 부분집합 $S$를 잡아서, 임의의 길이 $k$인 simple path 중 최소 하나의 정점이 $S$에 포함되게 하는 최소의 $\vert S \vert$를 구하는 문제이다. 먼저 이 문제를 dp로 접근하자. $dp[i]$는 $i$번 subtree만을 고려했을 때, 조건을 만족하는 주유소 개수의 최솟값이라 하자. $i$의 자식을 $c_1, \ldots, c_t$라 하자. 모든 길이 $k$인 경로는 어떤 $c_j$의 subtree 안에 완전히 속하거나, $i$를 포함하는 경로 두 가지 종류뿐이다. 그러므로 $c_j$ subtree 내에는 최소 $dp[c_j]$만큼의 주유소가 있어야 한다. 또한 각 자식의 subtree에서의 최적해를 union한 주유소 집합에, $i$ 정점에까지 주유소를 설치하면 이는 조건을 만족하는 주유소 집합이다. 따라서 다음이 성립한다. $$ \sum_{j=1}^t dp[c_j] \leq dp[i] \leq \sum_{j=1}^t dp[c_j] + 1$$

그러므로 $i$에 주유소를 반드시 설치해야만 하는지 여부를 구분해줄 수 있으면 dp 값들을 전부 계산할 수 있다. 이제 $i$로부터 각 subtree들로 path를 '침투'시킨다고 할 때, 주유소들을 피해 침투할 수 있는 최대 깊이를 생각하자. 좀 더 엄밀하게는, 자기 자신을 포함하여 ancestor들 중 주유소가 모두 설치되어있지 않은 정점의 최소 깊이가 침투 깊이이다. 이 때 $t \geq 2$이면 침투된 깊이가 가장 큰 것 두 개의 합이 $k$ 이상일 경우 $i$가 반드시 주유소여야 한다. (정확히 말하자면 $i$가 아니라 subtree 안쪽에 주유소를 하나 더 설치하는 것도 방법이지만, 어쨌든 주유소가 자식들 내부에서의 배치만으로는 부족하다는 관점에서) $t = 1$이면 유일한 침투된 깊이가 $k$ 이상인지 여부가 중요하다. 즉 각 subtree에서 계산했어야 하는 정보를 하나 더 발견했다. 이제 dp 정의를 다음과 같이 바꾼다: $dp[i]$는 $i$번 subtree만을 고려했을 때, 조건을 만족하는 주유소 배치 $S$들 중 ($\vert S \vert$, 침투 깊이) tuple의 사전순 최솟값이다.

dp 정의가 바뀌었으니, dp 전이도 다시 생각해봐야 한다. 자식 subtree 중 최적 개수보다 더 많은 주유소를 사용하느니, 자식들에선 최적 개수로 주유소를 두고 $i$에 주유소를 하나 더 설치하는 게 tuple의 두 번째 값에서 이득을 본다. 또 주유소를 추가로 설치하지 않는 걸 판별하기 위해서는 앞서 설명한 논리에 따라 자식 subtree 내의 주유소 배치가 전부 $dp[c_j]$가 지정하는 사전순 최소 tuple인 상태가 되도록 설치하여야 한다. 그러면 $dp[i]$ tuple의 첫 번째 값은 최적인지 아닌지 알 수 있고, 두 번째 값까지 최소화하는 방법을 생각해야 한다. 그런데 이것도 따지고 보면 간단하다. $i$에서 주유소 추가 설치가 필요한 케이스인 경우 당연히 $i$에 직접 설치하는 게 침투 깊이를 $0$으로 만들게 되므로 최소이고, 주유소 추가 설치가 필요하지 않다면 $i$에서부터의 침투 깊이는 자식 subtree들 중 최대 침투 깊이에 $+1$을 한 값이기 때문에 자식 subtree에서 사전순 최소 tuple을 사용하는 것이 이득이기 때문이다.

그러므로 dp 전이 과정에서 무조건 자식 dp값을 사용하는 것이 이득이고, greedy의 관점에서 이러한 greedy 전략이 정당함을 증명할 수 있다.

Logistical Warehouse 2 (2021 ICPC Seoul Regional)

트리와 $k$가 주어질 때, 반지름 $k$짜리 cover를 사용해서 모든 정점을 덮기 위한 최소의 개수를 묻는 문제이다. 위의 문제와 접근법이 거의 동일하지만, 이 증명은 좀 technical한 편이라 마음에 들진 않는 상태이다. 예전에 증명을 찾아봤는데 안 나와서 어떻게든 만들어봤다. 여기서는 바로 dp 정의를 서술한다. $dp[i]$를 $i$번 subtree만을 고려했을 때, $i$를 깊이 $0$으로 보았을 때 깊이가 $k$ 이하인 모든 정점을 덮는 cover 배치 $S$들 중 ($\vert S \vert$, $S$에 의해 아직 덮이지 않은 정점의 최대 깊이) tuple의 사전순 최소라고 정의하자. 이러한 정의의 motivation은, $i$ 정점으로부터 $k$만큼 아래에 있는 정점이 아직 덮이지 않은 경우, 그것을 덮을 수 있는 유일한 cover 위치가 $i$가 되게 하기 위한 방안이다.

위의 문제와 정확히 같은 방식으로, $i$를 구성하는 cover의 개수는 각 subtree 내의 cover의 최적 개수 합과 같거나 최대 $1$ 더 크다. ($i$를 중심으로 하는 cover를 두면 조건을 만족하므로) 이 때 $i$에 cover를 두어야 하는지 여부는, subtree들 중 덮이지 않은 정점의 최대 깊이들 중 어떻게 해도 $k-1$ 위치인 것이 있을 때 cover를 필요로 한다. 반대로 그렇지 않으면 cover가 필요하지 않으며, 이 경우 $dp[i]$에서 덮이지 않은 정점의 최대 깊이는 자식 subtree에서 덮이지 않은 정점들의 최대 깊이들의 최댓값에 $+1$한 값이다. 그러므로 역시 dp 전이가 greedy적으로 작동한다.

Fire Extinguishers (POI 2008/2009 Stage 1)

공식 에디토리얼도 존재하는 문제지만, 아직 증명을 이해하지 못 했다. 위와 같은 방식으로 증명이 가능할 거라고 생각하는데, 아직 모름.