c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q58 셀의 병합 패턴 (세번째 방법 - 동적계획법)

[문제]

N x N 개의 칸을 병합하는 가짓수를 구하고자 한다. (병합된 셀은 직사각 또는 정사각 형태여야 한다.)

예를 들어 2 X 2에서는 아래 8가지가 가능하다.

4 x 4 개의 칸을 병합하는 총 가짓수는? (추가로 1 x 1 칸이 없도록 할 때 그 가짓수는?)

 

[알고리즘#3] 

책에서 소개한 방법으로 동적계획법으로도 풀 수 있다.

이 방법을 사용하면 메모화도 필요 없으며 상당히 빠르게 답을 구할 수 있다.

방법은 다음과 같다.

예를 들어 아래와 같은 케이스가 있다고 하자.

4 x 4 칸이라면 내부에 9개의 격자점(빨간 점)이 존재한다.

각 격자점에는 아래와 같은 경계선이 존재한다.

 

위와 같이 각 격자점에는 경계선이 올 수 있는데, 각 격자점에 올 수 있는 경계선의 종류는 총 8가지이다.

U : 위쪽, D : 아래쪽, L : 왼쪽, R : 오른쪽

물론 경계선끼리는 서로 연결이 되어야 한다.

무슨 말이냐면 UDLR 옆에 UD 같은 것은 올 수 없다는 말이다. 

위와 같은 조합은 불가능하다.

왼쪽에 R이 있다면 오른쪽에는 반드시 L이 있어야 하고, 왼쪽에 R이 없다면 오른쪽에는 반드시 L이 없어야 한다.

 

문제를 단순화하기 위해서 3 x 3 에 대해서 문제를 풀어본다.

3 x 3이므로 내부에는 격자점이 2 x 2 개 존재한다.

2개의 경계선을 일렬로 나란히 배치할 수 있는 가짓수는 아래 그림처럼 총 34가지이다.

즉, 각 행에 올 수 있는 조합은 총 34가지이다. 

 

(R이 있는 것 * L이 있는 것) + (R이 없는 것 * L이 없는 것) = 5 * 5 + 3 * 3 = 34

이제 각 조합에 대해서 위로 뻗은 가지와 아래로 뻗은 가지를 살펴보자. 

위 그림의 경우 윗 가지는 [1 1]로 표현할 수 있고, 아랫 가지는 [1 0]으로 표현할 수 있다.

이를 비트로 생각하면 [3][2]와 같다.

각 [a][b] 조합에 대해서 개수를 세보면 다음과 같다.

합계 = 34

 

1층의 경우, 아랫 가지가 [0]인 것은 5개, [1]인 것은 8개, [2]인 것은 8개, [3]인 것은 13개이다.

이제 2층의 경우에 대해서 아랫가지가 각각 [0], [1], [2], [3]인 개수를 구해보자.

 

우선 2층의 아랫가지가 [0]인 개수는 어떻게 구할까.

1층의 아랫가지 조합과 2층의 윗가지 조합이 서로 일치하는 경우를 다 더하면 된다.

즉, 아래와 같이 구하면 된다.

2층의 [1] 개수도 마찬가지이다.

 

마찬가지로 2층의 [2], [3]도 구할 수 있다. (3 X 3일 때 정답은 322가지이다.)

 

위와 같은 계산은 곧 행렬의 곱셈을 한 것과 마찬가지이다.

 

만약, 3 x 4칸이라면? 3층까지 구하면 된다.

아래는 3 x 4칸일 때의 정답!

 

결국 이 문제에서 가장 중요한 것은 아래 테이블을 구하는 것이다. 그 다음부터는 단순한 행렬 곱셈 작업이다.

이 테이블을 구하는 것이 가장 중요하다.

만약 N = 4라면? 한 행에 격자점이 3개이므로 가지의 조합이 [0 0 0] 부터 [1 1 1]까지 가능할 것이다. 따라서 0 ~ 7까지 가능하다.

즉, [0][0] ~ [7][7]까지 각 수량을 구하면 된다.

 

이를 코드로 작성하면 다음과 같다.

#include <stdio.h>
#define M 7
#define N 7
#define W (M - 1)
#define H (N - 1)
#define SZ (1 << W) 
typedef unsigned long long ull;
enum {
    NONE, U = 0x1, D = 0x2, L = 0x4, R = 0x8, UD = U | D, LR = L | R,
    UDL = UD | L, UDR = UD | R, ULR = U | LR, DLR = D | LR, UDLR = UD | LR
};
int border[] = { LR, UDL, ULR, DLR, UDLR, NONE, UD, UDR }; // 0~4: L 포함, 5~7 : L 미포함
int table[SZ][SZ] = { 0 };

void getTable(int u, int d, int pre, int depth);
void copyArr(ull* arr1, ull* arr2, int sz);
int main() {
    int u = 0;
    int d = 0;
    int pre = 0;
    int depth = 0;
    getTable(u, d, pre, depth);
    /*
    for (int i = 0; i < SZ; i++) {
        for (int j = 0; j < SZ; j++) {
            printf("%d ", table[i][j]);
        }
        printf("\n");
    }
    */

    ull cnt[2][SZ] = { 0 };
    for (int i = 0; i < SZ; i++) {
        cnt[0][i] = 1;
    }
	
    for (int row = 0; row < H; row++) {
        int r = row % 2;
        int w = (row + 1) % 2;
        for (int i = 0; i < SZ; i++) {
            cnt[w][i] = 0;		// 쓰기 버퍼를 비워준다.
            for (int j = 0; j < SZ; j++) {
                cnt[w][i] += cnt[r][j] * table[j][i];    
                // cnt[새로운 층][0] = cnt[이전 층][0] * border[0][0] + cnt[이전 층][1] * border[1][0] + ...
            }
        }
    }

    ull result = 0;
    int r = H % 2;
    for (int i = 0; i < SZ; i++) {
        result += cnt[r][i];
    }
    printf("result = %llu\n", result);
}
void getTable(int u, int d, int pre, int depth) {

    if (depth == W) {
        table[u][d]++;
        return;
    }

    int sp = 0, ep = 0;
    if (depth == 0) {
        sp = 0, ep = 7;
    }
    else if (pre & R) {		// pre에 R이 있으면
        sp = 0, ep = 4;		// 0~4에서 선택 (L 포함)
    }
    else {                      // pre에 R이 없으면
        sp = 5, ep = 7;		// 5~7에서 선택 (L 미포함)
    }

    for (int i = sp; i <= ep; i++) {
        int up = (u << 1) + ((border[i] & U) != 0);	// border[i]에 U가 있으면 1을 더함
        int down = (d << 1) + ((border[i] & D) != 0);	// border[i]에 D가 있으면 1을 더함
        getTable(up, down, border[i], depth + 1);
    }
}
void copyArr(ull* arr1, ull* arr2, int sz) {
    for (int i = 0; i < sz; i++)
        arr1[i] = arr2[i];
}

3 x 4일 때의 정답

7 X 7 일 때도 순식간에 정답을 구할 수 있을 뿐 아니라

7 x 7일 때의 정답

 

오버플로우가 발생했을 수도 있어서 맞는 값인지는 모르겠지만 10 x 10인 경우에도 순식간에 계산을 할 수 있다.

 

단, 이 방법은 속도는 압도적으로 빠르지만, 문제에서 추가로 요구했던 1 x 1칸이 남지 않도록 병합하는 가짓수를 구하기 위해서는 코드를 많이 수정해야 한다.

이 부분에 한해서는 내가 떠올렸던 두번째 방법 - 비트마스크를 활용한 방법이 더 좋은 것 같다.