[Algorithm] cpp 백준 1648번: 격자판 채우기

2x1 도미노로 N×M 격자를 빈칸 없이 채우는 경우의 수를 9901로 계산. 열 너비 W를 최소로 두고 상태압축 비트마스크 DP로 스캔하며 수평/수직 배치 전이를 수행한다. 마스크 불변식으로 정당성을 보이고, 시간/공간 복잡도와 구현 포인트, 엣지 케이스(N·M 홀수=0)까지 정리했다.

문제

링크: https://www.acmicpc.net/problem/1648
요약: 2x1(또는 1x2) 도미노로 N×M 격자를 빈칸 없이 채우는 가짓수를 9901로 출력한다.

제한/스펙

1 ≤ N, M ≤ 14, 시간 2초, 메모리 128MB
정답을 9901로 나눈 나머지 출력

입출력

접근 개요

열 너비 W를 min(N, M)로 두고, 격자를 행(또는 열) 우선으로 한 칸씩 스캔한다.
길이 W의 비트마스크로 “현재 위치 포함 오른쪽으로 W칸 구간에서 위로부터 내려온 수직 도미노로 이미 점유된 칸” 상태를 관리한다.
현재 칸이 점유(mask의 LSB=1)이면 다음 칸으로 진행, 비어 있으면 수평(오른쪽) 또는 수직(아래) 배치를 시도한다.
메모이제이션된 DFS/DP로 상태 (pos, mask)를 캐싱하여 O(H·W·2^W) 시간에 해결한다(H=max(N,M)).

알고리즘 설계

상태: pos ∈ [0, H*W), mask ∈ [0, 1<<W)
- pos는 스캔 인덱스, mask의 LSB는 pos 칸의 점유 여부를 나타낸다.
전이:
- mask & 1 = 1이면 해당 칸은 이미 점유 → dfs(pos+1, mask>>1)
- 아니라면 두 선택지를 고려
  - 수평 배치: 같은 행에서 c+1 < W이고 다음 칸도 비어 있어야 함 → 새로운 마스크 (mask>>1) | 1
  - 수직 배치: 아래 행 존재(r+1 < H) → 새로운 마스크 (mask>>1) | (1<<(W-1))
기저: pos == H*W이면 mask == 0인 경우만 1을 반환
올바름(핵심 근거):
- 마스크는 아직 처리되지 않은 윈도우의 점유 상태를 정확히 추적하며, 수평/수직 전이는 도미노 배치의 유일한 두 경우만을 허용한다.
- 모든 칸을 좌→우, 상→하로 한 번씩 방문하므로 중복/누락 없이 완전 탐색이 되며, 동일 상태의 재방문은 메모이제이션으로 통합된다.

복잡도

시간: O(H·W·2^W) (W = min(N, M) ≤ 14)
공간: O(H·2^W)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

static const int MOD = 9901;

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

    int N, M;
    if (!(cin >> N >> M)) return 0;

    int H = max(N, M);
    int W = min(N, M);

    if ((H * W) % 2 == 1) {
        cout << 0;
        return 0;
    }

    vector<vector<int>> dp(H * W + 1, vector<int>(1 << W, -1));

    function<int(int, int)> dfs = [&](int pos, int mask) -> int {
        if (pos == H * W) return mask == 0 ? 1 : 0;
        int &res = dp[pos][mask];
        if (res != -1) return res;
        res = 0;

        int r = pos / W;
        int c = pos % W;

        if (mask & 1) {
            res = dfs(pos + 1, mask >> 1);
        } else {
            if (c + 1 < W && (mask & 2) == 0) {
                res += dfs(pos + 1, (mask >> 1) | 1);
                if (res >= MOD) res -= MOD;
            }
            if (r + 1 < H) {
                res += dfs(pos + 1, (mask >> 1) | (1 << (W - 1)));
                if (res >= MOD) res -= MOD;
            }
        }
        return res;
    };

    cout << dfs(0, 0) % MOD;
    return 0;
}

구현 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
from functools import lru_cache

sys.setrecursionlimit(1_000_000)
MOD = 9901


def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    N, M = map(int, data[:2])
    H, W = (N, M) if N >= M else (M, N)
    if (H * W) % 2 == 1:
        print(0)
        return

    @lru_cache(None)
    def dfs(pos: int, mask: int) -> int:
        if pos == H * W:
            return 1 if mask == 0 else 0
        r, c = divmod(pos, W)
        if mask & 1:
            return dfs(pos + 1, mask >> 1)
        total = 0
        if c + 1 < W and (mask & 2) == 0:
            total += dfs(pos + 1, (mask >> 1) | 1)
        if r + 1 < H:
            total += dfs(pos + 1, (mask >> 1) | (1 << (W - 1)))
        return total % MOD

    print(dfs(0, 0) % MOD)


if __name__ == "__main__":
    solve()