1. Brute-Force - 게임판 덮기(Boardcover) 문제

이 문제는 경우의 수를 세는 문제이므로 게임판을 덮을 수 있는 모든 경우를 생성하는 완전 탐색을 이용해 해결할 수 있다.

완전 탐색을 하기위해 재귀 호출 방법을 사용하는데,

이때 문제를 수행하는 과정의 하나의 조각을 게임판에 L자 블록을 하나 채워넣는 경우로 생각 할 수있다.

재귀함수는 L자 블록을 채워넣을 위치를 찾고 채워넣은 후의 게임판에 대해서 같은 과정을 반복하도록 재귀호출을 한다.

문제를 해결 할 때 같은 방법을 중복으로 세는 문제가 발생할 수 있다.

그 문제를 대비하기 위해 블록을 놓는 순서를 강제하는 방법을 쓰도록 하자.

즉, 재귀 호출의 각 단계마다 아직 채워지지않은 흰칸 중에서 제일 윗 줄이고 그중에서도 제일 왼쪽에 있는 칸을 덮도록 한다.

재귀 함수에서는 현재 채울 위치를 찾기 위해 게임판위 왼쪽 위부터 탐색 하도록 한다.

현재 채워넣을 위치는 흰 칸중에서 가장 윗줄, 왼쪽 칸이기 때문에 그 왼쪽과 위의 칸들은 모두 채워져있다고 생각 할 수있다.

따라서 위의 그림과 같이 4가지 타입으로 L자 블록을 채워넣을 수 있다.

현재 위치에서 블록을 채우기 위해 좌표를 이동시켜야 한다.

이 때 좌표를 바꿔주는 식을 매번 나눠서 써줄 수 없으므로 이동할 좌표 값을 다차원 배열에 저장해두는 것이 효율적이다.

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

{ {{0,0},{0,1},{1,0}},  // 1번 방법

{{0,0},{0,1},{1,1}},  // 2번 방법

{{0,0},{1,0},{1,1}},  // 3번 방법

{{0,0},{1,0},{1,-1}} };  // 4번 방법

위와 같이 4개의 타입으로 좌표를 이동하는 경우 각각의 타입에 대해서 좌표 이동 값을 저장해 둔다.

(1,-1) 의 경우는 행을 +1만큼 움직이고 열을 -1만큼 움직인다는 의미이다.

이차원 배열의 동적할당

문제의 게임판을 구현하기 위해 정수형의 이차원 배열이 필요하다.

이차원 배열 arr를 sizeX 행 sizeY 열로 동적할당은 다음과 같이 할 수 있다.

//arr[sizeX][sizeY]의 동적할당

int **arr = new int*[sizeX];

for(int i = 0; i < sizeX; i++){

arr[i] = new int[sizeY];

memset(arr[i], 0, sizeof(int)*sizeY);  // 0으로 초기화

}

문제 풀이

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int h;  // 행 수

int w;  // 열 수

int res = 0;  // 방법 수

const int coverType[4][3][2] =  // 블록을 덮는 방법(행,열)

{ {{0,0},{0,1},{1,0}},

{{0,0},{0,1},{1,1}},

{{0,0},{1,0},{1,1}},

{{0,0},{1,0},{1,-1}} };

bool set(int type, int x, int y, int **board, int delta) {

bool result = true;

for (int i = 0; i < 3; i++) {

int nextX = x + coverType[type][i][0];

int nextY = y + coverType[type][i][1];

if (nextX < 0 || nextY < 0 || nextX >= h || nextY >= w) {  // x,y 좌표가 보드판 범위를 벗어나면 오류

result = false;

}

else if ((board[nextX][nextY] += delta) > 1) {  // 보드판에 1을 더했는데 보드판 값이 1보다 커지면 기존에 채워져있었던 것 -> 오류

result = false;

}

}

return result;

}

void coverBoard(int **board) {

int x = -1;

int y = -1;

// 보드판의 왼쪽 위에서부터 탐색하면서 채워져있지않은 위치의 좌표값을 구함

for (int i = 0; i < h; i++) {

for (int j = 0; j < w; j++) {

if (board[i][j] == 0) {

x = i;

y = j;

break;

}

}

if (x != -1) break;

}

if (x == -1) { // 보드판이 다 채워져있으면 방법 수 +1

res++;

return;

}

for (int type = 0; type < 4; type++) {

if (set(type, x, y, board, 1)) { // 해당 타입으로 보드를 채울 수 있으면 채우고

coverBoard(board);  // 남은 보드판에 대해서 재귀 함수 호출

}

set(type, x, y, board, -1);  // 다른 타입으로 보드를 채우기 위해 이전에 채웠던것을 복구해놓음

}

}

int main() {

int c;  // 테스트 케이스 수

vector<int> result;

cin >> c;

for (int i = 0; i < c; i++) {

cin >> h;

cin >> w;

int **arr = new int*[h];

for (int j = 0; j < h; j++) {

arr[j] = new int[w];

}

for (int row = 0; row < h; row++) {

char input[20];

cin >> input;

for (int col = 0; col < w; col++) {

if (input[col] == '.') arr[row][col] = 0;

else arr[row][col] = 1;

}

}

coverBoard(arr);

result.push_back(res);

res = 0;

}

for (int i = 0; i < c; i++) {

cout << result[i] << endl;

}

}

set(...) 함수는 매개변수로 받는 type 번호에 따라서 해당 타입으로 L자 블록을 놓고 블록이 겹치지 않고 놓였는지 여부를 리턴한다.

board[nextX][nextY] 에 delta 값을 더하는 것은 해당 위치에 블록을 놓는 것을 의미한다.

만약 지금 블록을 놓았는데 칸의 값이 1 이상이면 이전에 이미 해당 칸이 채워져 있었다는 것을 의미한다. (이전에 해당 칸의 값이 0이 아니었다)

그러면 False 값을 반환한다.

그리고 현재 위치에서 하나의 타입에 대해서 재귀 호출을 통해 게임판 덮기를 끝내고 돌아오면 그 타입에 의해 놓은 블록을 제거해야 한다.

그러기 위해서 다른 함수를 따로 구현하지 않고 set(...) 함수에 delta 값을 -1로 전달해주면

기존에 L자 블록을 놓았던 칸의 값에 -1을 하기 때문에 블록을 제거하는 효과를 얻을 수 있다.