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

[문제]

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

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

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

 

 

[알고리즘 #1]

일단 직관적으로 떠오르는 방법은 map[N][N]을 만들어서, [1][1]에서부터 차례로 숫자를 채워나가는 것이다.

(같은 숫자를 가진 칸들은 병합된 칸을 의미한다.)

 

예를 들어, 아래 [x][y]에 숫자를 채워넣으려고 할 때 총 4가지 케이스가 가능하다.

 

1) map[x][y-1] == map[x-1][y]인 경우, (이 때는 필연적으로 map[x-1][y-1] 역시 같은 숫자이다.)

이 때 노란색 칸에 올 수 있는 숫자는 3 뿐이다.

 

2) map[x-1][y-1] == map[x][y-1]인 경우,

 이 때 노란색 칸에는 3은 올 수 없고, 4가 오거나 아니면 새로운 숫자 (5)가 올 수 있다.

 

3) map[x - 1][y - 1] == map[x - 1][y]인 경우,

이 때 노란색 칸에는 3은 올 수 없고, 4 또는 새로운 숫자(5)가 올 수 있다.

 

4) 그 밖의 경우 

이 때 노란색 칸에는 4, 5가 올 수 있으며, 새로운 숫자(6) 역시 가능하다.

 

temp[4] 배열을 만들어 { map[x-1][y-1], map[x][y-1], map[x-1][y], reserve(새로운 숫자) }를 저장하고, 각 케이스에 맞게 꺼내서 사용한다.

이를 코드로 나타내면 다음과 같다.

#include <stdio.h>
#define N 4

int map[N + 1][N + 1] = { 0 };

void solve(int* cnt, int x, int y, int reserve);
void printMap(int map[][N + 1]);
int main() {

    int cnt = 0;
    int x = 1, y = 1;
    int reserve = 1;
    solve(&cnt, x, y, reserve);
    printf("cnt = %d\n", cnt);
}

void solve(int* cnt, int x, int y, int reserve) {

    if (x == N + 1  && y == N) {
        (*cnt)++;
        return;
    }
    if (x == N + 1) {
        solve(cnt, 1, y + 1, reserve);
        return;
    }

    int temp[4] = { map[x - 1][y - 1], map[x][y - 1], map[x - 1][y], reserve };
    for (int i = 0; i < 4; i++) {
        if (y == 1) {
            if (x == 1) {
                if (i != 3) {
                    continue;
                }
            }
            else {
                if (i < 2) {
                    continue;
                }
            }
        }
        else if (x == 1) {
            if (i == 0 || i == 2) {
               continue;
            }
        }
        else if (temp[1] == temp[2]) {
            if (i != 0) {
                continue;
            }
        }
        else if (temp[0] == temp[1]) {
            if (i == 0 || i == 1) {
                continue;
            }
        }
        else if (temp[0] == temp[2]) {
            if (i == 0 || i == 2) {
                continue;
            }
        }
        else {
            if (i == 0) {
                continue;
            }
        }
        map[x][y] = temp[i];
        int newReserve = i == 3 ? reserve + 1 : reserve;
        solve(cnt, x + 1, y, newReserve);
        map[x][y] = 0;
    }
}

정답은 다음과 같으며 순식간에 구할 수 있다.

 

그러나  이 방법으로는 5 X 5에서는 다소 시간이 오래 걸리며,

무엇보다도 문제에서 추가로 요청한 1 x 1칸이 존재하지 않는 케이스의 개수를 구하려면 코드를 많이 수정해야 한다.