Connection Profile DP

이 글은 비트마스크 DP를 배경지식으로 합니다.

격자에서 비트마스크 DP를 돌리는 문제가 있습니다. 예를 들어 BOJ 1648 (격자판 채우기) 문제에서는 위에서 아래로, 왼쪽에서 오른쪽으로 훑으면서, 최근 M개의 칸의 상태를 비트마스크로 저장합니다. 각 칸의 상태는 그 칸에 도미노가 채워졌으면 1, 아니면 0입니다. 그림으로 나타내면 이렇게 되겠죠.

Connection Profile??

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

이 문제를 풀어봅시다.

격자에서 연결 요소를 만들되 비용의 합을 최소화하는 문제입니다. 위에서 다룬 것처럼 비트마스크 DP를 하고 싶어집니다. 최근 M개의 칸의 상태를 비트마스크로 저장합니다. 각 칸의 상태는 그 칸이 연결 요소에 포함되어 있으면 1, 아니면 0입니다.

하지만 그러면 안 됩니다. 최근 M개의 칸이 사용되었는지 아닌지만 따져서는 연결 요소가 생겼는지 알 수 없기 때문입니다. 예를 들어, 아래 그림에서 최근 M개의 칸의 상태가 왼쪽과 같을 때, 가운데처럼 모든 칸이 연결되었는지, 오른쪽처럼 모든 칸이 연결되지 않았는지 알 방법이 없습니다.

그렇다고 지금까지 본 모든 칸의 상태를 다 저장하면 당연히 안 됩니다.

그래서 우리는 어떤 칸들이 서로 연결되어 있는지를 저장할 겁니다. 연결 요소에 번호를 붙였다고 해봅시다. 단, 선택되지 않은 칸은 0으로 채워넣습니다.

이제 최근 M개의 칸의 상태만 저장해 놓으면 됩니다!

상태 전이

상태 전이를 분석해 봅시다.

케이스 1: "현"을 선택하지 않는다.

"현"을 선택하지 않으면, "현"의 위쪽 칸을 제외하여 최근 M-1개의 칸의 상태가 하나씩 밀리고, 최근 칸의 상태는 0이 됩니다.

단, 이 케이스를 따라가면 안 되는 경우가 하나 있습니다. "현"의 위쪽 칸이 선택되었고, 최근 M-1개의 칸 중 누구와도 연결되어 있지 않을 때입니다.

이때는 "현"을 선택하지 않는 순간, 

• 만약에 최근 M-1개의 칸 중 선택된 칸이 존재한다면, 위쪽 칸은 나머지 칸들과 하나의 연결 요소를 이루는데 실패하게 됩니다. 
• 만약에 최근 M-1개의 칸 중 선택된 칸이 없다면, 모든 칸이 하나의 연결 요소를 이루는 데에는 성공했으나, "이미 하나의 연결 요소가 있었다"는 정보가 소실됩니다. 그래서 "현" 이후의 칸들을 선택해야 하는지 말아야 하는지를 결정할 수 없습니다.

따라서 이 상황에서는 케이스 1을 건너뛰어야 합니다.

케이스 2: "현"을 선택한다.

이때는 "현"의 위쪽 칸과 왼쪽 칸의 상태에 따라 세 가지 경우가 생깁니다.

(1) 위쪽 칸과 왼쪽 칸이 선택되지 않았다면, "현"은 그 자체로 새로운 연결 요소를 이루게 됩니다. 따라서 최근 M개의 칸에서 사용하지 않은 연결 요소 번호를 새로 만들어 그 칸에 집어넣습니다.

(2) 위쪽 칸과 왼쪽 칸 중 하나만 선택되었다면, 그 칸의 연결 요소의 번호를 "현"이 그대로 따라갑니다.

(3) 위쪽 칸과 왼쪽 칸이 모두 선택되었다면, 두 칸의 연결 요소가 하나로 합쳐집니다. 두 칸의 연결 요소 번호를 각각 x와 y라고 할 때, 최근 M-1개의 칸 중 번호가 y인 것들의 번호가 x로 바뀝니다. (물론 x에서 y로 바꿀 수도 있습니다.) 그리고 "현"은 그 번호를 그대로 따라갑니다.

풀이의 마무리

마지막으로, 선택된 칸들이 연결 요소를 이룰 때마다 정답을 갱신해 주면 됩니다. 선택된 칸들이 연결 요소를 이루는지 판별하려면 서로 다른 양수가 1개 이하인지 검사하면 됩니다.

아쉽게도, N=M=9인 입력을 아무거나 넣어 보면 너무 느리다는 것을 알 수 있습니다.

최적화

물론 연결된 칸끼리는 같은 번호를 가지니 DP 상태의 개수가 M^M개나 되지는 않겠지만, 제가 구현한 바로는 칸 하나를 볼 때마다 7만 개의 상태가 생겼습니다.

이를 최적화하려면 같은 상태들을 하나로 합쳐 줘야 합니다. 예를 들어 다음 두 상태는 같습니다. 연결 요소들에 번호만 다시 붙여 주면 같아지기 때문입니다. 상태 전이를 하면서 최근 M개의 칸의 상태를 "정규화"하는 과정이 필요합니다.

간단한 방법으로 사전순으로 가장 앞선 상태로 정규화하는 방법이 있습니다. 위쪽 칸에서부터 하나씩 보면서, 상태가 0이면 그대로 0으로 둡니다. 양수이면서 이전에 만난 적 없는 번호면, 새로운 번호를 할당합니다. 이전에 만난 적 있는 번호면, 그 번호가 할당받았던 새로운 번호를 그대로 줍니다. 예를 들어 위 그림의 오른쪽 상태는 왼쪽 상태로 정규화됩니다.

위에 언급했듯이 인접한 칸은 같은 번호를 가지므로 정확한 시간 복잡도를 분석하기는 어렵지만, 적당한 상한은 잡아줄 수 있습니다. 정규화를 했기 때문에, 최근 M개의 칸의 상태로 가능한 조합의 개수는 M개의 칸을 몇 개의 집합으로 분할하는 방법의 수보다 작거나 같습니다. 그 수는 bell number라고 하고, 0번째 bell number부터 차례대로 나열한 수열이 OEIS에 번호 A000110으로 있습니다. 9번째 bell number는 21,147입니다. 적당한 상한만 잡은 건데도 위에서 보았던 7만 개보다 훨씬 적고, 실제로 돌려 보면 나타나는 상태의 개수는 2천 개밖에 되지 않습니다.

정규화 작업까지 해 주고 N=M=9인 입력을 넣어 보면 답이 순식간에 나오는 것을 확인할 수 있고, 저의 구현은 0.1초 안에 맞았습니다!! 를 받았습니다.