커넥션 프로파일 DP (Broken Profile DP)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 2분 · 667자/단어 #algorithm #dp #dp-connection-profile #bitmask

정의

커넥션 프로파일 DP (Broken Profile DP) 는 직사각형 격자를 tile-by-tile 로 처리하면서, 처리된 영역과 아직 처리되지 않은 영역의 경계 (broken profile) 를 bitmask 와 같은 작은 상태로 압축해 DP 에 사용하는 기법. 도미노/트리미노 타일링, 격자 배치 문제에서 널리 쓰인다.

문제 상황과 동기

H x W 격자를 1x2 / 2x1 도미노로 빈틈없이 덮는 경우의 수. Naive: exponential search 2^(HW). H ≤ 10, W ≤ 10 에도 HW 만 100, 완전탐색 불가.

핵심 통찰: 셀 단위 스캔에서 경계면의 모양만 알면 앞으로 필요한 정보가 충분. W 가 작을 때 2^W 가지 mask 로 상태 표현 가능.

시각화

핵심 아이디어

격자 (r, c) 를 row-major 순서로 한 칸씩 처리. 경계선은 W 개의 구역으로 나뉨.

Profile bitmask (W bits):
  bit j (j >= c): cell (r, j) 가 이미 채워졌는가? (horizontal overflow)
  bit j (j < c):  cell (r+1, j) 가 아래에서 채워졌는가? (vertical overflow)

DP transition at cell (r, c):
  if mask bit c == 1:   # 이미 채워짐 (왼쪽에서 horizontal)
      clear bit c, move on
  if mask bit c == 0:   # 빈 칸
      - place vertical    -> set bit c (next row 의 이 칸이 채워짐)
      - place horizontal  -> set bit c+1 (같은 row 오른쪽 칸이 채워짐)

셀이 채워진 후 해당 bit 는 “past” 섹션으로 넘어가 자동으로 “아래에서 덮인” 의미로 전환.

알고리즘

dp[mask] = 현재 위치까지 처리, profile = mask 일 때 경우의 수

initialize dp[0] = 1
for r = 0..H-1:
    for c = 0..W-1:
        for mask = 0..(1<<W)-1:
            if dp[mask] == 0: continue
            if mask & (1 << c):   # already filled
                ndp[mask ^ (1 << c)] += dp[mask]
            else:                 # empty
                ndp[mask | (1 << c)] += dp[mask]           # vertical
                if c+1 < W and !(mask & (1 << (c+1))):
                    ndp[mask | (1 << (c+1))] += dp[mask]   # horizontal
        dp = ndp

answer = dp[0]   # 마지막 row 끝난 후 mask = 0

구현

// Domino tiling: H x W grid, 1x2 / 2x1 dominoes, MOD = 9901
#include <bits/stdc++.h>
using namespace std;
const int MOD = 9901;
int main() {
  int h, w; cin >> h >> w;
  int sz = 1 << w;
  vector<int> dp(sz, 0);
  dp[0] = 1;
  for (int r = 0; r < h; r++) {
      for (int c = 0; c < w; c++) {
          vector<int> ndp(sz, 0);
          for (int mask = 0; mask < sz; mask++) {
              int val = dp[mask];
              if (val == 0) continue;
              if (mask & (1 << c)) {
                  ndp[mask ^ (1 << c)] = (ndp[mask ^ (1 << c)] + val) % MOD;
              } else {
                  ndp[mask | (1 << c)] = (ndp[mask | (1 << c)] + val) % MOD;
                  if (c + 1 < w && !(mask & (1 << (c + 1)))) {
                      ndp[mask | (1 << (c + 1))] = (ndp[mask | (1 << (c + 1))] + val) % MOD;
                  }
              }
          }
          dp = move(ndp);
      }
  }
  cout << dp[0] << "\n";
  return 0;
}

MOD = 9901
h, w = map(int, input().split())
sz = 1 << w
dp = [0] * sz
dp[0] = 1
for r in range(h):
  for c in range(w):
      ndp = [0] * sz
      for mask in range(sz):
          val = dp[mask]
          if val == 0:
              continue
          if mask & (1 << c):
              ndp[mask ^ (1 << c)] = (ndp[mask ^ (1 << c)] + val) % MOD
          else:
              ndp[mask | (1 << c)] = (ndp[mask | (1 << c)] + val) % MOD
              if c + 1 < w and not (mask & (1 << (c + 1))):
                  ndp[mask | (1 << (c + 1))] = (ndp[mask | (1 << (c + 1))] + val) % MOD
      dp = ndp
print(dp[0])

import java.util.*;
import java.io.*;
public class Main {
  static final int MOD = 9901;
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int h = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());
      int sz = 1 << w;
      int[] dp = new int[sz];
      dp[0] = 1;
      for (int r = 0; r < h; r++) {
          for (int c = 0; c < w; c++) {
              int[] ndp = new int[sz];
              for (int mask = 0; mask < sz; mask++) {
                  int val = dp[mask];
                  if (val == 0) continue;
                  if ((mask & (1 << c)) != 0) {
                      ndp[mask ^ (1 << c)] = (ndp[mask ^ (1 << c)] + val) % MOD;
                  } else {
                      ndp[mask | (1 << c)] = (ndp[mask | (1 << c)] + val) % MOD;
                      if (c + 1 < w && (mask & (1 << (c + 1))) == 0) {
                          ndp[mask | (1 << (c + 1))] = (ndp[mask | (1 << (c + 1))] + val) % MOD;
                      }
                  }
              }
              dp = ndp;
          }
      }
      System.out.println(dp[0]);
  }
}

stdin

2 4

결과

복잡도

항목	값
시간	O(H * W * 2^W)
공간	O(2^W)
실용 범위	W ≤ 18 (2^18 = 262k)

변형 / 활용

변형	설명
Plug DP	broken profile 의 일반화. 비도미노 타일, Hamiltonian path 검색
3D tiling	3차원 격자, L-tromino 등 다양한 조각
Grid coloring	인접 조건이 있는 격자 coloring (예: chessboard pattern)
Subset DP	상태 압축 일반 기법. TSP 등과 유사

함정

1. W 가 큰 경우

W > 18 이면 상태 2^W 가 감당 불가. W 큰 case 는 다른 접근 (분할 정복, transfer-matrix + exponentiation) 필요.

2. Horizontal overflow 처리

Horizontal 을 놓을 때 c+1 < W 검사와 함께 !(mask & (1 << (c+1))) (오른쪽 칸이 비었음) 도 반드시 확인.

3. 마지막 행 검증

마지막 셀까지 처리한 후 dp[0] 만 유효. mask != 0 은 아직 피우지 못한 칸이 있거나 vertical 이 경계를 넘은 것.

4. MOD 경계

경우의 수가 폭발적으로 증가하므로 MOD (9901 등) 로 나누는 것 필수.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 1648	격자판 채우기	-	kokoa-lab
BOJ 1823	도미노 채우기	-	kokoa-lab
BOJ 2711	오타맨	-	kokoa-lab

참고

이 글의 용어 (3개)

동적 계획법 (Dynamic Programming)algorithm: 정의 동적 계획법 (Dynamic Programming, DP) 은 큰 문제를 작은 부분 문제로 나누고, 각 부분 문제의 최적해를 저장하여 중복 계산을 제거하는 최적화 기법. R…
비트마스크 DP (Bitmask DP)algorithm: 정의 비트마스크 DP (Bitmask DP) 는 상태 공간이 부분집합 으로 표현될 때, 각 부분집합을 정수의 비트로 인코딩해 DP 상태로 삼는 기법. N ≤ 20 범위에서 O(2…
SOS DP (Sum Over Subsets)algorithm: 정의 SOS DP (Sum Over Subsets) 는 길이 2^N 의 배열 a 에 대해, 모든 mask (0..2^N-1) 마다 mask 의 부분 집합 (submask) 에 대…