CS and mathematics

문제 해석

Directed graph \(G(V,E)\)가 주어지는데, \(G\)의 각 정점마다 “체력”이 있다. 처음에는 정점 \(1\)만 \(1\)의 체력을, 나머지는 \(0\)의 체력을 가지고 있고, 모든 정점의 체력을 \(0\)으로 만드는 것이 목표이다.

임의의 정점 \(i\)에 \(u_i\)의 비용으로 약한 충격, 또는 \(z_i\)의 비용으로 강한 충격을 줘서 체력을 \(1\) 감소시킬 수 있는데, 약한 충격은 강한 충격보다 비용이 적지만 각 정점 \(j\)에 대하여 \(j\)의 체력을 간선 \((i, j)\)의 개수만큼 증가시킨다. 최소 비용을 구해라.

접근

정점 \(i\)의 체력을 \(1\) 깎는 최소 비용을 \(dp[i]\)라고 두면 강한 충격을 줄 때와 약한 충격을 줄 때를 비교하는 내용의 식을 세울 수 있다:

\[dp[i] = \min \left(z_i, \ u_i + \sum_{(i, j) \in E} dp[j] \right) \quad\cdots (1)\]

정점 \(1\)부터 DFS를 돌며 \(dp\) 값들을 계산하되, back edge를 밟으면(사이클을 찾으면) \(\infty\)를 return해서 반드시 강한 충격을 선택하는 전략으로 구현을 하면 예제는 (당연히) 안 틀리고, 제출을 해보면 틀린다. 예제는 정점 \(2\)의 self-loop만 빼면 DAG라서 이렇게 풀어도 정답이 나왔지만 더 긴 사이클을 만들어 보면 금방 반례가 나온다.

5
1 100 2 2 5
1 5 1 3
3 30 1 4
3 20 1 5
1 10 1 2

위 방법에 의하면 간선들을 입력 순서대로 방문한다고 할 때 \(u_1 + z_2 + z_5=16\)이 나오지만 정답은 \(u_1 + u_5 + 2z_2=12\)이다. 이렇게 사이클을 포함하는 그래프 위에서 정의된 DP를 단순 탐색으로 풀려고 하면 사이클이 어느 정점에서 탐지되는지에 따라 답이 바뀐다는 문제점이 있다.

올바른 풀이는 그래프의 위상에 의한 순서가 아니라 DP 값의 오름차순으로 DP 값들을 결정하는 것으로, Dijkstra 최단경로 알고리즘의 일반화라고 말할 수 있다. 이 원리에 대한 직관을 얻기 위해서 DAG에서의 최단거리 문제로 잠시 주제를 옮겨보자. DAG에서의 최단거리 문제는 가장 기본적인 그래프 DP로서 아래 식으로 표현되고, 정점들을 위상 순서(topological order)로 보면서 이 식을 사용하면 \(f\) 값들을 모두 찾을 수 있다:

\[f(j) = \min_{(i,j) \in E} f(i) + d(i,j) \quad\cdots (2)\]

이 방법은 음수 가중치 간선이 있어도 문제 없이 동작하지만, 음수 가중치 간선이 없다는 조건을 추가해 보자. 그러면 \(f(i) > f(j)\)인 간선은 \(\min\)에서 볼 필요가 없어진다:

\[f(j) = \min_{ \begin{align} (i,j) &\in E \\ f(i) &\le f(j) \end{align} } f(i) + d(i,j) \quad\cdots (3)\]

이제 위상 순서 대신 \(f\)가 단조증가하는 순서로 정점들을 본다면 어떻게 되는지 보자. 정점들의 permutation \(a_1..a_n\)이 \(i \le j \Leftrightarrow f(a_i) \le f(a_j)\)를 만족한다고 하자. \(i, j\)를 \(a_i, a_j\)로 교체하고 \(a_1..a_n\)의 정의를 사용하면 다음을 얻는다:

\[f(a_j) = \min_{ \begin{align} (a_i,a_j) &\in E \\ i &< j \end{align} } f(a_i) + d(a_i,a_j) \quad\cdots (4)\]

\(\min\)에 생긴 \(i < j\) 조건에 주목하자(등호는 self-loop이므로 버려도 된다). 이것은 \(f(a_1)..f(a_k)\)를 알면 \(f(a_{k+1})\)을 구할 수 있다는 뜻으로, \(f(a_1)..f(a_n)\) 순서로 계산하는 것이 가능함을 의미한다. 정점을 보는 순서를 바꾼 이후 그래프가 acyclic하다는 조건을 쓰지 않았으므로, 이 방법은 음수 가중치 간선만 없으면 사이클이 있어도 동작한다.

마지막으로 \(a_1..a_n\)를 어떻게 아는가 하는 의문이 남는데, 그 답은 사실 간단하다. \(f(a_1)..f(a_k)\)를 알면 \(f(a_{k+1})\)을 구할 수 있기 때문에, \(f(a_1)..f(a_k)\)를 아는 시점에 \(f\)를 계산할 수 있는 정점이 반드시 하나 이상 있다. 식 \((4)\)에 의해 이 정점들의 \(f\)값은 기존 모든 \(f\)값보다 크거나 같으며, 그 중에 \(f\)가 최소인 것이 \(a_{k+1}\)이다. 이 과정을 우선순위 큐를 활용하여 효율적으로 구현한 것이 바로 Dijkstra의 최단경로 알고리즘이다.

이제 본 문제로 돌아와 결론을 내 보자. 식 \((1)\)에 있는 \(\min\)의 두 operand를 실시간으로 추적하는 \(f[i], g[i]\)를 선언하고, \(dp[i] = z_i\) 기준으로 초기화하자. \(dp[i]\)의 참값은 \(z_i\) 이하이므로 Dijkstra 알고리즘에서 거리값들을 \(\infty\)로 초기화하는 것과 대응한다.

\[\begin{array}{lll} f[i] := & dp[i] & \leftarrow z_i \\ g[i] := & u_i + \sum_{(i, j) \in E} dp[j] & \leftarrow u_i + \sum_{(i, j) \in E} z_j \end{array}\]

이제 \(f[j] > g[j]\)인 정점 중에서 \(g[j]\)가 최소인 정점 \(j\)를 골라서 \(f[j] \leftarrow g[j]\)로 확정한 다음 \((i, j) \in E\)인 정점 \(i\)들에게 전파하고, 반복하면 된다. \(f[j]\)가 확정된 것을 \(i\)에게 전파하여 update된 \(g[i]\)는 \(f[j]\)보다 작지 않으므로, Dijkstra 알고리즘에서 음수 가중치 간선이 없는 것과 대응한다. \(f[j]\)가 \(2\)회 이상 확정되는 경우는 없음을 Dijkstra 알고리즘과 같은 방법으로 증명할 수 있으며, 시간 복잡도도 동일하게 \(\mathcal{O}(E \log E)\)이다.

코드

7981.cpp

참고문헌

M. Sniedovich (2006). Dijkstra’s algorithm revisited: the dynamic programming connexion. Control and Cybernetics, vol. 35 No. 3.

참고