[문제링크]
ACM-ICPC 2007년 세계결선(in Tokyo)의 J번입니다. 먼저 이 문제의 원래 에디토리얼(by Derek Kisman)을 참고하여 주시기 바랍니다.
일단 이 문제는 의도하였던 것 이상으로 대회 최악의 함정 문제였습니다. 여러 팀의 많은 시도가 있었지만 단 1팀도 맞추지 못 하였고, 아예 이 문제를 건드리지 않은 대학이 1위, 2위를 차지할 정도였습니다. 문제는 얼핏 쉬워보이지만 섣부른 직관으로 세운 알고리즘은 곧바로 반례를 발견하게 되는, 그런 골치아픈 문제입니다.
문제는 간단합니다 - 첩자가 당신의 기지에 침입하였습니다. 기지는 여러 개의 방과 방들 사이/또는 바깥으로 연결하는 터널로 이루어져 있습니다. 각 방에는 카메라가 장착되어 있어 당신은 언제든지 첩자가 어디에 있는지 쉽게 알아챌 수 있습니다. 첩자가 밖으로 도망가기 전에 터널을 폭파하여 도주로를 차단해야 합니다. 단, 첩자를 '터널 안에' 가둘 수는 없습니다(터널을 통과하는 중에 폭파시켜 매몰시키는 것은 불가능합니다).
첩자는 항상 밖으로 도망가기 위해 노력을 할 것이고, 기지 구조를 잘 알고 있습니다. 당신은 첩자의 움직임을 잘 살피며 가능한 최소한의 개수의 터널을 폭파하여 스파이를 기지에서 도망가지 못하게 하려 합니다. 이 때 필요한 터널 수를 구하는 문제입니다.
Derek Kisman의 원래 에디토리얼에도 잘 나와있지만, 누구나 처음에는 이 문제를 매우 쉬운 Min-cut/Maximum flow 문제로 보고 접근하기 쉽습니다. 대회 참가자 조 모 군은 dijkstra 알고리즘과 maximum flow를 적절히 혼합하여 상당수의 예를 커버하는 해법을 내놓았지만, 대회가 끝난 후 토론하는 자리에서 다른 참가자가 곧 반례를 제시해서 조 군을 좌절케하기도 하였습니다.
대회를 참관하며 제가 이 문제의 해법이 Maximum-flow를 잘 모델링하거나, 또는 node마다 Maximum-flow와 관계없는 어떠한 식을 가지고 fixpoint를 구하는 것이 아닐까 생각을 했었습니다만, 의외로 해법은 'Maximum-flow와 관계있는 어떠한 식을 가지고 fixpoint를 구하는' 것이었습니다.
[spoiler="더 보기..."]여기서 잠깐> 그래프의 fixpoint를 구한다는 것에 대해 생소하게 여길 분들이 많으리라 생각합니다: 이해하려면 약간의 수학적인 개념이 필요하지만 알고리즘 자체는 간단합니다. 그래프의 각 node마다 식이 있습니다. 그 식은 혼자 계산한다고 바로 답이 나오는 것이 아니라, 다른 node에 적힌 수식을 계산한 값에 영향을 받게 되어 있습니다. 이러한 형태의 연립방정식을 풀기 위한 방법입니다.
예를 들어, 다음과 같은 연립방정식이 있다고 합시다:
A0 = {1, 4}
A1 = A0 ∪ A2 ∪ {1}
A2 = A1 ∪ {2}
A3 = A2 ∪ (A1 - {4})
이 때, A0~A3의 초기값을 공집합 ({})으로 두고, 더 이상 아무 것도 변하지 않을 때까지 각 식들을 반복해서 계산하면 저 연립방정식의 해를 구할 수 있습니다. 물론, 이 때는 여러가지 사항을 고려해야 하는데, 그 중 간단한 몇 가지만 설명합니다 :
그 식에 의해 계산된 결과는 monotone 한가? : 항상 단조증가하거나 단조감소하여야 합니다. 위 식의 경우, 대부분의 연산이 집합의 합집합으로 이루어져 있고, 차집합 연산은 항상 한쪽이 상수이기 때문에 단조성을 보장할 수 있습니다 :)
끝이 있는가? : 항상 끝나야 합니다. 위 식에서는 등장하는 모든 상수들의 집합 {1, 2, 4}의 크기가 유한하기 때문에 항상 끝난다고 말할 수 있습니다. :)
Derek Kisman이 쓴 에디토리얼에 나오는 d-number가 이러한 개념과 상통합니다 :)
[/spoiler]
직관은 의외로 간단합니다 : 지금 첩자가 u라는 방에 있다고 합시다. 이 때, 첩자가 다른 방에 있을 때 각각 우리가 부숴야 하는 터널의 수(d-number)를 알고 있다고 가정하면, 우리는 다음과 같은 전략들을 세울 수 있습니다 :
지금 이 순간, 첩자가 아예 밖으로 나가지 못하게 모든 병목구간을 차단합니다. 이 때 부숴야 할 터널의 수는 max-flow를 통해 구할 수 있습니다.
터널을 아예 부수지 않고, 첩자가 다른 방으로 움직이는 것을 지켜봅니다. 이 때 최종적으로 부수게 될 터널의 수는
max ((foreach v ∈V and v!=u) d[v]) 입니다.
y라는 값을 둡시다. d[v]<=y(v ∈V and v!=u) 인 방 v에 대해서는 첩자가 그 방으로 움직이고 나서를 생각합니다. 다만, d[v]>y인 방들을 통해서는 절대 외부로 나갈 수 없게 미리 터널을 부숩니다. 미리 부숴야 할 터널을 x라 하면, 각 y에 대해 (x+y)의 최소값을 구합니다. d[v]>y인 방을 통해서만 외부로 나가는 경우에 대한 max-flow를 구하면 x의 값을 쉽게 구할 수 있습니다.
물론, 세번 째 전략이 앞에 두 전략들을 포함하는 이야기입니다. 그렇다면 우리는 d[u]를 처음에 적당히 큰 값으로(저같은 경우, 모든 노드에 대해 1번 전략을 선택했을 때를 initial value로 잡았습니다.) 두고 fixpoint solution을 구하는 방식으로 됩니다 :)
fixpoint를 구하는 간단한 iterative worklist algorithm은 다음과 같습니다:
[spoiler="더 보기..."]workset := {all nodes}
while(workset != empty)
d[u] = min(d[u], calculate(u))
if (d[u] is changed)
[/spoiler]
얼핏 비효율적으로 보이는 이 알고리즘은, 사실 정말 비효율적입니다(-_-;; ). 반복 횟수를 최소화하기 위해 여러가지 기법이 고안되어 있습니다(active/wait list를 구분한 worklist algorithm 등). 저 반복 횟수를 획기적으로 줄이는 것을 목표로 아직도 많은 연구자들이 머리를 싸매고 있습니다. ^^
lazyboy
[문제링크]
ACM-ICPC 2007년 세계결선(in Tokyo)의 J번입니다. 먼저 이 문제의 원래 에디토리얼(by Derek Kisman)을 참고하여 주시기 바랍니다.
일단 이 문제는 의도하였던 것 이상으로 대회 최악의 함정 문제였습니다. 여러 팀의 많은 시도가 있었지만 단 1팀도 맞추지 못 하였고, 아예 이 문제를 건드리지 않은 대학이 1위, 2위를 차지할 정도였습니다. 문제는 얼핏 쉬워보이지만 섣부른 직관으로 세운 알고리즘은 곧바로 반례를 발견하게 되는, 그런 골치아픈 문제입니다.
문제는 간단합니다 - 첩자가 당신의 기지에 침입하였습니다. 기지는 여러 개의 방과 방들 사이/또는 바깥으로 연결하는 터널로 이루어져 있습니다. 각 방에는 카메라가 장착되어 있어 당신은 언제든지 첩자가 어디에 있는지 쉽게 알아챌 수 있습니다. 첩자가 밖으로 도망가기 전에 터널을 폭파하여 도주로를 차단해야 합니다. 단, 첩자를 '터널 안에' 가둘 수는 없습니다(터널을 통과하는 중에 폭파시켜 매몰시키는 것은 불가능합니다).
첩자는 항상 밖으로 도망가기 위해 노력을 할 것이고, 기지 구조를 잘 알고 있습니다. 당신은 첩자의 움직임을 잘 살피며 가능한 최소한의 개수의 터널을 폭파하여 스파이를 기지에서 도망가지 못하게 하려 합니다. 이 때 필요한 터널 수를 구하는 문제입니다.
Derek Kisman의 원래 에디토리얼에도 잘 나와있지만, 누구나 처음에는 이 문제를 매우 쉬운 Min-cut/Maximum flow 문제로 보고 접근하기 쉽습니다. 대회 참가자 조 모 군은 dijkstra 알고리즘과 maximum flow를 적절히 혼합하여 상당수의 예를 커버하는 해법을 내놓았지만, 대회가 끝난 후 토론하는 자리에서 다른 참가자가 곧 반례를 제시해서 조 군을 좌절케하기도 하였습니다.
대회를 참관하며 제가 이 문제의 해법이 Maximum-flow를 잘 모델링하거나, 또는 node마다 Maximum-flow와 관계없는 어떠한 식을 가지고 fixpoint를 구하는 것이 아닐까 생각을 했었습니다만, 의외로 해법은 'Maximum-flow와 관계있는 어떠한 식을 가지고 fixpoint를 구하는' 것이었습니다.
[spoiler="더 보기..."]여기서 잠깐> 그래프의 fixpoint를 구한다는 것에 대해 생소하게 여길 분들이 많으리라 생각합니다: 이해하려면 약간의 수학적인 개념이 필요하지만 알고리즘 자체는 간단합니다. 그래프의 각 node마다 식이 있습니다. 그 식은 혼자 계산한다고 바로 답이 나오는 것이 아니라, 다른 node에 적힌 수식을 계산한 값에 영향을 받게 되어 있습니다. 이러한 형태의 연립방정식을 풀기 위한 방법입니다.
예를 들어, 다음과 같은 연립방정식이 있다고 합시다:
A0 = {1, 4}
A1 = A0 ∪ A2 ∪ {1}
A2 = A1 ∪ {2}
A3 = A2 ∪ (A1 - {4})
이 때, A0~A3의 초기값을 공집합 ({})으로 두고, 더 이상 아무 것도 변하지 않을 때까지 각 식들을 반복해서 계산하면 저 연립방정식의 해를 구할 수 있습니다. 물론, 이 때는 여러가지 사항을 고려해야 하는데, 그 중 간단한 몇 가지만 설명합니다 :
16년 전