[Algorithm Strategies] 03. Exhaustive Search - Board Cover

1. Exhaustive Search

1.1 Board Cover - Recursive Function

1.1.1 Problem

- H  ✕ W 크기의 게임판이 있는데, 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있음

   - 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮고 싶음

     - 자유롭게 회전 가능, 서로 겹치거나 검은 칸을 덮거나 게임판 빡으로 나가서는 안됨

 - 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램 작성

   - 입력 첫 줄에는 테스트 케이스의 수가 주어짐

     - 각 테스트 케이스의 첫 줄에는 두 개의 정수 H, W가 주어지고 H줄에 W 글자로 게임판의 모양이 주어짐

1.1.2 Algorithm Strategy

- 각 삼각형을 덮는 방식은 4가지 방식이 존재

   - ㄱ, ㄱ 반대, ㄴ, ㄴ 반대로 구성, 따라서 게임판이 주어질 때 4가지 방식에 대해 확인하는 함수가 필요

const int coverType[4][3][2];

 - 게임판에 랜덤으로 선택하여 좌표를 선택 후 ㄱ 모양의 좌표를 생성한다면 중복이 나타날 수 있음

   - 중복을 허용하지 않기 위해 처음 좌표로 부터 오른쪽, 이 후 한칸 밑으로 이동 및 오른쪽으로 비어있는 공간 확인

 - 모든 좌표에 대해 경우의 수를 세어야 하므로 완전 탐색을 사용하여 재귀 함수 사용

int Exhaustive::cover(vector<vector<int>>& board);

 - 마지막으로 타입에 대한 정보를 넘겨 3가지의 방식을 사용할 수 있도록 설정

   - 또한 delta 값을 넘겨 블록을 놓는 역할 및 치우는 역할을 설정

bool Exhaustive::set(vector<vector<int>>& board, int y, int x, int type, int delta);

1.1.3 implementation

1.1.3.1 Main Function

- H를 3, W를 7로 설정하여 게임판을 생성

/* H - 3, W - 7 */
Exhaustive exhaustive;
string str;  vector<vector<int>> board(3);
for (int i = 0; i < board.size(); i++)
{
    getline(cin, str);
    for (int j = 0; j < str.size(); j++)
    {
        if (str[j] == '#') board[i].push_back(1);
        else board[i].push_back(0);
    }
}
cout << exhaustive.cover(board) << endl;

1.1.3.2 Cover Function

 - 함수가 시작됨으로써 중복을 없애기 위해 채우지 못한 곳에서 가장 윗줄 중 왼쪽에 있는 칸을 설정

   - 이때 더 이상 값이 없는 경우 종료 및 1개의 값을 더함

int y = -1, x = -1;
for (int i = 0; i < board.size(); i++)
{
    for (int j = 0; j < board[i].size(); j++)
        if (board[i][j] == 0) { y = i; x = j; break; }
    if (y != -1) break;
}
if (y == -1) return 1;

 - 위에서 사용한 도형 4가지를 사용하기 위해 반복문을 4번 사용

   - 도형이 넣을 수 있는 지 확인하고 사용한 도형은 다시 설정하지 못하게 설정

     - 만약 도형이 넣을 수 있다면 재귀 함수를 통해 다음에 넣을 수 있는 공간을 찾아 모두 찾을 경우 종료

int ret = 0;
for (int type = 0; type < 4; type++)
{
    if (set(board, y, x, type, 1)) ret += cover(board);
    set(board, y, x, type, -1);
}
return ret;

1.1.3.3 Set Function

 - 4가지 모양의 도형을 빈 공간에 넣어야 하므로 위에서 설명한대로 배열로 생성하여 사용

   - 밑의 배열 코드는 4개의 도형, 즉 ㄱ, ㄱ 반대, ㄴ, ㄴ 반대로 이루어짐

const int coverType[4][3][2] =
{	{ {0, 0}, {1, 0}, {0, 1} },
	{ {0, 0}, {0, 1}, {1, 1} },
	{ {0, 0}, {1, 0}, {1, 1} },
	{ {0, 0}, {1, 0}, {1, -1} } };

   - 원래 위치에서 도형의 위치를 더함으로써 그 위치의 값이 게임판에 포함하는 지 확인

     - 또한 delta 값을 사용하여 게임판에 도형을 사용했다는 걸 알림, 즉 도형을 치우는 느낌을 설정

bool ok = true;
for (int i = 0; i < 3; i++)
{
    const int ny = y + coverType[type][i][0]; const int nx = x + coverType[type][i][1];

    if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) ok = false;
    else if ((board[ny][nx] += delta) > 1) ok = false;
}
return ok;