습격자 초라기는 복잡한 case work이 가미된 원형 DP 문제로 잘 알려져 있고, 웬만한 그리디 풀이는 사풀이며 반례가 반드시 존재한다는 것이 상식이었다. 그러나 오늘 pyb1031님이 PS갤러리에 그리디로 AC를 받은 코드를 인증했다. 즉시 스트레스 테스트를 돌려봤지만 반례가 나오지 않았고, 좀 더 생각해 본 결과 맞는 풀이라는 확신이 들었다. 이 글에서는 이 풀이가 무엇을 하는지, 왜 맞는지를 다룬다.

풀이

원형 DP를 선형 DP로 바꿀 때처럼 1번 세로줄과 $N$번 세로줄에 걸치는 도미노에 대한 case work은 동일하다.

일단 문제를 선형으로 바꿨으면, 남아있는 칸들을 가지고 그래프를 만든다. 각 칸에 대해 노드를 하나씩 만들고, 두 칸을 동시에 커버할 수 있을 때 두 노드를 엣지로 연결한다.

이제 이 그래프에서 degree가 0인 노드는 무시하고, degree가 1인 노드가 있으면 그 두 칸을 짝지어 주고 그 두 개의 노드를 제거한다. 이 과정을 degree가 1인 노드가 없을 때까지 반복한다.

남은 그래프에서 맨 왼쪽 세로줄부터 보면서 다음과 같이 진행한다.

  • 한 세로줄에 두 칸이 남아있고 그 두 칸 사이에 엣지가 있으면 그 둘을 매칭한다.
  • 그렇지 않고 각각의 칸에 대해 오른쪽 칸과 연결된 엣지가 있으면 오른쪽 칸과 매칭한다.

정답은 이렇게 해서 얻은 매칭의 개수를 $2N$에서 빼면 된다.

증명

case work을 통해 원형으로 연결된 그래프를 선형으로 끊었으므로 남은 그래프는 이분 그래프이다.

degree가 1인 노드는 매칭에 포함시켰을 때 절대 손해를 보지 않는다. 남은 노드들로 최대 이분 매칭을 구했을 때, 제외된 노드에서 시작하는 augmenting path가 있으면 매칭을 1 추가할 수 있고, 없으면 이웃한 노드가 반드시 어떤 다른 노드와 매칭되어 있다는 뜻이므로 이 매칭을 바꿔서 같은 크기의 매칭을 만들 수 있기 때문이다.

degree가 1인 노드를 모두 반복적으로 매칭했으면, 남은 그래프에서 모든 노드는 degree가 2 이상이다. 이제 여기서 그리디하게 매칭했을 때 최적이 아닌 매칭을 얻었다고 가정해 보자. 그러면 반드시 매칭에 포함되지 않으면서 augmenting path의 끝점이 되는 노드가 존재한다. 그러한 노드 중에 가장 왼쪽의 노드를 $X$라고 하자. 이 노드 또한 최초에 degree가 2 이상이어야 하는데, 왼쪽에서 오른쪽으로 진행하는 그리디의 특성상 이 노드에서 오른쪽으로 가는 엣지가 존재하면 이 엣지를 막을 방법이 없으므로, 왼쪽과 세로 방향으로 엣지가 있어야 함을 알 수 있다.

이 노드의 직전 세로줄에 세로 방향 매칭이 있으면 그리디가 매칭을 시도하는 순서에 의해 세로 방향 매칭이 되므로, 이 노드가 매칭되지 않게 하는 방법은 다음의 두 가지 방법밖에 없다.

...   O=O-...
        |
... O=O-X

... O=O-X
        |
...   O=O-...

여기서 =가 매칭에 사용된 엣지, -와 |는 매칭에 사용되지 않은 엣지이다.

$X$의 반대편 노드에서 오른쪽으로 가는 엣지가 있을 수도 있고 없을 수도 있다. 그러나 그러한 엣지가 없으면 $X$가 포함된 연결 요소에 $X$와 augmenting path를 통해 연결할 다른 노드가 없으므로 모순이고, 있더라도 augmenting path를 통해 오른쪽으로 넘어가야 하는데 parity가 맞지 않기 때문에 연결이 불가능하다. 따라서 모순이고, 이러한 $X$는 존재하지 않는다는 결론을 얻는다. 따라서 이 그리디를 통해 얻는 매칭은 최대 매칭임을 증명하였다.

틀린 버전과 반례

왼쪽부터 보는 부분에서 가로 엣지를 세로 엣지보다 먼저 보는 경우는 다음과 같은 반례가 있다.

입력
1
7 3
3 1 1 1 1 1 3
3 1 1 2 2 1 3

출력
10

정답 출력
9

예상 난이도

이 풀이를 처음 보면 누가 와도 “이게 왜 됨?” 할 것이다. degree 1인 노드를 제거하는 부분까지는 생각해낼 만 하지만, 남은 부분에서 왼쪽부터 1 pass에 최대 매칭을 얻을 수 있을 것이라고는 상상하기 매우 어렵고, 정당화하기도 어렵다. 1 pass 부분의 디테일에 따라 AC와 WA가 갈리기 때문에 더욱더 그렇다. 이 풀이에 난이도를 매기자면 플1이나 다이아까지도 볼 수 있다고 생각한다.