c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q58 셀의 병합 패턴 (두번째 방법 - 비트 마스크 및 메모화, 해시테이블)

[문제]

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

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

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

 

[알고리즘#2]

이 문제는 다음과 같이 생각할 수도 있다.

[0]칸을 포함하는 병합 셀의 가짓수는 총 16가지이다. 

(병합 셀의 크기: n x n, 단 n = 1, 2, 3, 4 - 총 16가지)

이 각각의 병합 셀을 마스크라고 하자.

이제 이 [0]에 위 16가지 마스크 중 1가지를 배치하고, [1]로 넘어간다. 

예를 들어 [0]에 아래와 같이 배치했다고 하자.

[1]은 이미 채워져 있으므로, 다음 칸인 [2]로 이동한다.

[2]에는 다음과 같이 8가지 마스크가 가능하다.

단, [2]칸에 놓아야 하므로 마스크를 비트 이동 시킨다. mask << 2

[2]칸에 위 8가지 마스크 중 1가지를 배치한다.

예를 들어 다음과 같이 배치했다고 하자.

이제 [3] ~ [7]은 건너뛰고 [8]로 넘어간다.

[8]에는 다음과 같이 4가지 마스크가 가능하다.

단, [8] 위치에 놓아야 하므로 시프트 시킨다. mask << 8

[8]에 놓기 위해서 시프트 (mask << 8)

 

이런 식으로 반복해 나가는 것이다.

이렇게 마스크를 놓을 수 있는 총 가짓수를 구하면 된다.

 

위 맵에서 각 자리를 비트라고 생각할 수 있다.

위 예시에서는 2^0 자리의 자리에 0x33 마스크를 배치한 후, 2^2 자리에 (0x3333) << 2 마스크를 배치한 것이다.

 

이를 코드로 구현하면 다음과 같다.

// 비트 연산 및 메모화 기능 사용

#include <stdio.h>
#include <stdbool.h>
#define N 4
#define SZ (N * N)
#define MAX ((1 << SZ) - 1)
typedef unsigned long long ull;

ull mask[SZ] = { 0 };
int memo[MAX + 1] = { 0 };

int solve(ull map, int pos);
int main() {

    // mask 생성
    for (int i = 0; i < SZ; i++) {
        if (i == 0) {
            mask[i] = 1;
        }
        else if (i < N) {
            mask[i] = (mask[i - 1] << N) + 1;
        }
        else {
            mask[i] = (mask[i - N] << 1) + mask[i % N];
        }
    }

    ull map = 0;
    int pos = 0;
    printf("cnt = %d\n", solve(map, pos));
}

int solve(ull map, int pos) {
    if (memo[map]) {
        return memo[map];
    }

    if (pos == SZ) {
        return 1;
    }

    // 만약 pos 위치에 1이 채워져 있으면 다음으로 이동
    if ((map & (1 << pos)) != 0) {
        solve(map, pos + 1);
        return;
    }

    int max = (SZ - 1) - (pos % N) * N;
    // pos = 0, 4, 8, 12 이면 max = 15 (모든 마스크 사용 가능)
    // pos = 1, 5, 9, 13 이면 max = 11 (F, FF, FFF, FFFF 사용 불가)
    // pos = 2, 6, 10, 14 이면 max = 7 (7, 77, 777, 7777, F, ... 사용 불가)

    int cnt = 0;
    for (int i = 0; i <= max; i++) {
        // 위 max 조건과 아래 조건을 통해서 pos에 올 수 있는 마스크 한정
        if (i % N > N - 1 - pos / N)
            continue;
        
        ull newMask = 0;
        newMask = mask[i] << pos;
        
        if ((newMask & map) != 0) {
            continue;
        }
        ull newMap = newMask | map;
        cnt += solve(newMap, pos + 1);
    }
    memo[map] = cnt;
    return memo[map];
}

 

특정 map 상태에서부터 셀을 병합할 수 있는 총 가짓수를 memo[map]에 저장해두면 상당히 빠르게 답을 구할 수 있다.

5 X 5 맵에서도 금방 답을 구할 수 있을 뿐만 아니라

5 x 5 맵에서의 병합 가능한 가짓수

문제에서 추가로 요청한 1 x 1 칸은 없는 경우의 수도 쉽게 구할 수 있다.

마스크 배열에서 1 x 1 마스크는 사용하지 않으면 된다. 즉, 아래와 같이 수정하면 됨.

4 x 4 맵에서 1 x 1칸이 없도록 병합하는 가짓수

 

단, 이 문제에서는 아래 2가지 이유로 메모 배열을 이용한 메모 기법이 좋은 방법이 아니다.

1) 메모장 최대 사이즈 제한

N = 5까지는 메모장 생성이 가능하나, N >= 6에서는 메모장의 사이즈가 2 ^ (36) 이상이 되므로 메모장 생성이 불가능하다.

2) 메모장 활용률

N = 5만 되어도 메모장의 크기는 2 ^ 25 = 33554432 이므로 상당히 크다. 그러나 정작 메모장에 실제로 기록되는 숫자는 수천개에 불과하다. 즉, 메모장의 상당 공간은 사용되지 않는다는 것이다. 이는 너무나 비효율적이다.

 

따라서, 이 문제에서는 메모 배열보다는 해시 테이블을 활용해야 한다.

해시 테이블 관련해서는 따로 포스팅할 계획이다.

간단히 설명하면, 이 문제의 경우 map 자체를 인덱스로 활용하지 말고, map을 해시 값으로 변환한 뒤 이 값을 테이블의 인덱스로 사용하는 것이다

해시 값을 만드는 방법은 여러가지가 있을 수 있는데, 보통 소수로 나눈 나머지를 활용하는 경우가 많은 것 같다.

물론 2개 이상의 map이 공통된 해시 값을 가질 수도 있는데 (충돌이라고 표현한다.) 이 경우에는 연결 리스트를 활용한다.

 

해시 테이블을 활용한 코드는 다음과 같다.

// 비트 연산 및 해시테이블 사용

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define N 7
#define SZ (N * N)
#define MAX ((1ULL << SZ) - 1)
#define TABLE_SIZE 1000003

typedef unsigned long long ull;
typedef struct node {
    ull key;
    ull value;
    struct Node* next;
} Node;

ull mask[SZ] = { 0 };
Node* table[TABLE_SIZE] = { NULL };

ull solve(ull map, int pos);
int hash(ull key);			// 해시값을 만드는 함수
Node* find(ull key);			// key를 가지는 node의 주소를 반환하는 함수
void insert(ull key, ull value);	// key 및 value를 가지는 node를 추가하는 함수
int main() {

    // mask 생성
    for (int i = 0; i < SZ; i++) {
        if (i == 0) {
            mask[i] = 1;
        }
        else if (i < N) {
            mask[i] = (mask[i - 1] << N) + 1;
        }
        else {
            mask[i] = (mask[i - N] << 1) + mask[i % N];
        }
    }

    ull map = 0;
    int pos = 0;
    printf("cnt = %llu\n", solve(map, pos));

    for (int i = 0; i < TABLE_SIZE; i++) {
        Node* cur = table[i];

        while (cur) {
            Node* next = cur->next;
            free(cur);
            cur = next;
        }
    }
}
ull solve(ull map, int pos) {
	
    Node* node = find(map);
    if (node)
        return node->value;

    if (pos == SZ) {
        return 1;
    }

    // 만약 pos 위치에 1이 채워져 있으면 다음으로 이동
    if ((map & (1ULL << pos)) != 0) {
        return solve(map, pos + 1);
    }

    int max = (SZ - 1) - (pos % N) * N;
    ull cnt = 0;
    for (int i = 0; i <= max; i++) {
        // 위 max 조건과 아래 조건을 통해서 pos에 올 수 있는 마스크 한정
        if (i % N > N - 1 - pos / N)
            continue;
            
        ull newMask = mask[i] << pos;

        if ((newMask & map) != 0) {
            continue;
        }
        ull newMap = newMask | map;
        cnt += solve(newMap, pos + 1);
    }
    insert(map, cnt);
    return cnt;
}
int hash(ull key) {
    return key % TABLE_SIZE;
}
Node* find(ull key) {
    int idx = hash(key);
    Node* cur = table[idx];

    while (cur != NULL) {
        if (cur->key == key) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
void insert(ull key, ull value) {
    int idx = hash(key);
    
    Node* cur = table[idx];
    while (cur != NULL) {
        if (cur->key == key) {
            cur->value = value; // 이미 있으면 값만 업데이트 후 종료
            return;
        }
        cur = cur->next;
    }
    
    Node* node = (Node*)malloc(sizeof(Node));

    node->key = key;
    node->value = value;
    node->next = table[idx];
    table[idx] = node;
}

해시 테이블을 활용하면 N = 7에 대해서도 빠르게 답을 구할 수 있다.