C++로 2×n 그리드의 보드를 색칠하는 모든 경우의 수 구하기

문제 소개

2개의 행과 n개의 열로 이루어진 그리드가 주어졌다고 가정해 봅시다. 이 그리드는 서로 겹치지 않는 n개의 보드로 완전히 덮여 있으며, 각 보드는 빨강(red), 파랑(blue), 초록(green) 중 하나의 색으로 칠해야 합니다. 단, 서로 맞닿아 있는 두 보드는 같은 색으로 칠할 수 없고, 특별한 제약이 없다면 세 가지 색을 모두 사용할 필요도 없습니다.

그리드의 배치는 배열 'grid'로 주어집니다. 같은 영문자로 표시된 칸들은 하나의 보드에 해당하고, 서로 다른 영문자는 서로 다른 보드를 의미합니다. 우리가 구해야 할 값은 주어진 조건을 만족하도록 보드를 색칠하는 방법의 총 개수입니다.

예를 들어 n = 4이고 grid = {"abbd", "accd"}가 입력으로 주어지면 출력은 6이 됩니다. 즉, 조건을 만족하는 색칠 방법은 총 6가지입니다.

접근 방식

핵심 아이디어는 그리드를 두 종류의 블록으로 나누는 것입니다. 위아래 두 칸이 같은 문자라면 세로로 세워진 보드 하나이고, 그렇지 않다면 2×2 영역을 차지하는 가로 보드 쌍입니다. 왼쪽에서 오른쪽으로 훑으며 각 블록의 종류를 기록한 뒤, 이전 블록과 현재 블록의 조합에 따라 경우의 수를 곱해 나가는 동적 계획법(DP)으로 문제를 해결할 수 있습니다.

세로 보드 하나를 칠하는 방법: 3가지
가로 보드 쌍(2×2 영역)을 칠하는 방법: 위 보드 3가지 × 아래 보드 2가지 = 6가지

블록 사이의 전이 규칙은 다음과 같습니다.

가로 쌍 → 가로 쌍: ×3
가로 쌍 → 세로 보드: ×1 (위·아래 색이 이미 서로 다르므로 선택지가 1가지뿐)
세로 보드 → 가로 쌍: ×2
세로 보드 → 세로 보드: ×2

결괏값이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 저장합니다. 전체 시간 복잡도는 O(n)으로 효율적입니다.

알고리즘 단계

이 문제를 해결하기 위해 다음 단계를 따릅니다.

MODVAL := 10^9 + 7
배열 s 정의
i := 0으로 초기화, i < n인 동안 반복:
   만약 grid[0, i]와 grid[1, i]가 같다면:
      s의 끝에 1 삽입
      (i를 1 증가)
   그렇지 않다면:
      s의 끝에 2 삽입
      i := i + 2
배열 tvec 정의
만약 s[0]이 1이라면:
   tvec[0] := 3
그렇지 않다면:
   tvec[0] := 6
i := 1로 초기화, i < s의 크기인 동안 반복(i를 1씩 증가):
   만약 s[i - 1] == 2이고 s[i] == 2라면:
      tvec[i] := tvec[i - 1] * 3 mod MODVAL
   만약 s[i - 1] == 2이고 s[i] == 1이라면:
      tvec[i] := tvec[i - 1]
   만약 s[i - 1] == 1이고 s[i] == 2라면:
      tvec[i] := tvec[i - 1] * 2 mod MODVAL
   만약 s[i - 1] == 1이고 s[i] == 1이라면:
      tvec[i] := tvec[i - 1] * 2 mod MODVAL
tvec[s의 크기 - 1] 반환

C++ 구현 예제

더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int n, vector<string> grid){
    int MODVAL = 1e9 + 7;
    vector<int> s;
    for (int i = 0; i < n;) {
        if (grid[0][i] == grid[1][i]) {
            s.push_back(1);
            i++;
        } else {
            s.push_back(2);
            i += 2;
        }
    }
    vector<int> tvec(s.size());
    if (s[0] == 1)
        tvec[0] = 3;
    else
        tvec[0] = 6;
    for (int i = 1; i < (int)s.size(); i++) {
        if (s[i - 1] == 2 && s[i] == 2)
            tvec[i] = tvec[i - 1] * 3 % MODVAL;
        if (s[i - 1] == 2 && s[i] == 1)
            tvec[i] = tvec[i - 1];
        if (s[i - 1] == 1 && s[i] == 2)
            tvec[i] = tvec[i - 1] * 2 % MODVAL;
        if (s[i - 1] == 1 && s[i] == 1)
            tvec[i] = tvec[i - 1] * 2 % MODVAL;
    }
    return tvec[s.size() - 1];
}
int main() {
    int n = 4;
    vector<string> grid = {"abbd", "accd"};
    cout << solve(n, grid);
    return 0;
}

입력

4, {"abbd", "accd"}

출력

이처럼 그리드를 블록 단위로 분해하고 전이 규칙만 정확히 적용하면, 복잡해 보이는 색칠 문제도 선형 시간 안에 간단히 해결할 수 있습니다.