타일 채우기 문제를 푸는 테크닉 1

이 게시글에서는 타일을 채우는 것과 관련한 문제에서 특수한 경우에 사용하는 기술을 알아본다.

N * M 크기 격자의 상태를 정수 한 개로 표현하기

https://atcoder.jp/contests/abc196/tasks/abc196_d

D - Hanjo

길이가 1, 2인 블럭으로 H * W 크기의 격자를 채우는 가짓수를 출력하는 문제이다.

이 문제는 $HW \leq 16$이라는 조건과 이러한 타일링 문제에 적용되는 성질로 인해 재미있는 생각을 떠올릴 수 있다.

1. 어떤 행에서 길이 2의 타일을 배치한다고 해보자. 그러면 당신은 가로로 2칸을 배치하거나 세로로 2칸을 배치할 수 있다.

2. 그리디하게 한 행을 모두 채우고 다음 행으로 갔을 때 이전 행에서 세로로 배치된 블록의 상태를 고려하여 마지막 행까지 타일을 채울 수 있을 것이다.

여기서 관심사는 세로로 배치 했을 때 다음 행에서 그 정보를 알아내는 방법이다. 행마다 비트마스크를 구성해야 하는 걸까?

놀랍게도 그럴 필요 없다. $HW \leq 16$ 이기 때문이다.

1칸씩 순서대로 번호를 메긴다면 다음과 같이 번호를 매길 수 있을 것이다. 세로로 배치된 블록의 숫자를 주목하라.

세로로 배치 했을 때 다음 행으로 넘어간 부분의 번호는 바로 이전 행에서 배치된 번호 + 열의 크기가 되는 것이다. (4 + 3 = 7, 5 + 3 = 8)

즉, 우리는 이것을 이용해서 정수 단 한 개로 상태를 표현할 수 있게 된다.

단지 int 정수 한개로 16칸의 정보를 관리하면서 길이 2의 블록을 세로로 배치할 때 다음 행에 놓이는 위치의 비트 번호를 1로 만들면 상태 관리를 아주 간단하게 할 수 있다.

다음은 위에서 말한대로 정수 한 개로 상태를 관리하면서 DFS로 문제를 해결하는 코드이다.

#include <bits/stdc++.h>

using namespace std;

int h, w, a, b, res;

void dfs(int idx, int bt, int a, int b)
{
    if (idx == h * w)
        ++res;
    
    if (bt & (1 << idx))
        dfs(idx + 1, bt, a, b);

    if (b)
        dfs(idx + 1, bt | (1 << idx), a, b - 1);

    if (a)
    {
        if (!(bt & (1 << (idx + 1))) && idx % w < w - 1)
            dfs(idx + 2, bt | (1 << idx) | (1 << (idx + 1)), a - 1, b);
        
        if (idx + w < w * h && !(bt & (1 << (idx + w))))
            dfs(idx + 1, bt | (1 << idx) | (1 << (idx + w)), a - 1, b);
    }
}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> h >> w >> a >> b;
    dfs(0, 0, a, b);
    cout << res;
}

비트 구간을 스위핑

다음으로 백준 저지에 수록된 문제를 보자

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

1648번: 격자판 채우기

이 문제도 유사해보이지만 N과 M이 최대 14로 g++ C++ 기준 196(14 * 14) 비트를 표현할 수 있는 정수는 존재하지 않는다.

그럼 어떻게 푸는 걸까? 앞에서 말한 그리디하게 칸을 채우는 것을 적용해보자.

우리는 앞을 다 채운 상태일 때 앞으로 채울 칸의 일부만 고려하여 영리하게 DP를 수행할 수 있다. 그 일부는 무엇일까? 바로 M이다.

이 문제를 푸는데에는 다음과 같은 아이디어가 이용된다.

현재 위치~M칸 만큼의 상태만 비트마스크로 관리한다. 한 칸씩 이동할 때마다 비트마스크에 대해 오른쪽으로 쉬프트를 1회 하면 현재 위치의 비트를 버리고 바로 한 칸 옆으로 갔을 때 비트마스크를 얻을 수 있게 된다.

도달한 칸이 비어있다면(비트가 0이면) 그 다음 행은 당연히 비어있다. 현재 위치에서 정확히 M칸 이동하면 다음 행의 동일 열에 도달한다. 따라서 세로로 타일을 배치하고자 한다면 현재 비트마스크에서 (1 << (M - 1)) 의 비트를 1로 만들어 타일을 세로로 배치한 상태를 표현할 수 있다.

현재 위치(비트 1)은 쉬프트 해서 없어지기 때문에 딱히 채우지 않아도 된다.

이렇게 하면 비트 쉬프트를 하면서 첫 비트가 1인 경우를 만나면 이전 행에서 세로로 배치한 것이므로 바로 다음 위치로 이동하면 된다.

마찬가지로 가로로 타일을 배치할 때도 두 비트가 비어있는지 확인 후 현재 비트마스크에서 두 번 쉬프트 하면 된다.

단, 현재 위치가 마지막 열일 경우를 유의한다. 마지막 열에서 가로로 2칸을 채운다는 것은 타일을 반으로 나눠서 하나씩 배치하는 꼴이 되기 때문이다. 따라서 마지막 열일 경우는 가로로 2칸 채우는 연산을 해서는 안된다.

타일을 전부 채웠는지 확인하는 방법은 무엇일까?

N * M + 1 번째 위치에 도달했을 때 비트마스크가 0이면 다 채운 것이다.

비트마스크가 0이기 때문에 없는 위치에 타일이 채워지지 않았고 이전 위치는 그리디하게 타일을 전부 채웠기 때문이다.

위에서 설명한 계산을 하기 위해 필요한 테이블은 DP[N * M + 1][1 << (M + 1)]로 두어 문제를 풀 수 있다.

다음은 격자판 채우기를 DP로 해결한 코드이다.

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define mod 9901

using namespace std;

int n, m;
int dp[14 * 14 + 1][1 << 15];

int memo(int block, int bt)
{
    if (block > n * m)
        return 0;
    if (block == n * m && !bt)
        return 1;
    
    int &ret = dp[block][bt];
    if (ret != -1)
        return ret;
    ret = 0;

    int tmp = 0;

    if (bt & 1)
        tmp = (tmp + memo(block + 1, bt >> 1)) % mod;
    else
        tmp = (tmp + memo(block + 1, (bt | (1 << m)) >> 1)) % mod;

    if (!(bt & 3) && (block + 1) % m != 0)
        tmp = (tmp + memo(block + 2, bt >> 2)) % mod;

    ret += tmp;
    ret %= mod;
    return ret;
}

int main()
{
    memset(dp, -1, sizeof dp);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;

    cout << memo(0, 0);
}

지금까지 격자 전체, 혹은 일부를 비트마스크로 관리하면서 타일링 문제를 푸는 방법을 알아보았다.

타일링 문제를 풀면서 재미있는 테크닉을 발견하면 더 공유하도록 하겠다.