[알고스팟] 게임판 덮기 - 완전 탐색, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

게임판 덮기(링크)

빈 곳이 있는 게임판이 주어질 때 L 모양의 블럭을 한 개씩 덮어 모든 칸을 채우는 방법의 가짓수를 계산한다.

재귀적으로 생각하기

게임판에 L 모양의 블럭을 한 개 덮는 것을 하나의 작업 조각으로 생각한다. 재귀 함수는 빈 곳이 있는 게임판이 주어질 때 4 가지 모양의 L 블럭을 각각 덮을 수 있는지 검사해보는 작업을 반복한다.

중복으로 세는 문제

블록을 놓는 순서에 상관없이 같은 블록들로 덮었다면 한 가지 경우이다. 블록을 놓는 순서를 강제하면 놓는 순서에 따라 별개의 경우로 세는 문제를 막을 수 있다. 가장 왼쪽 위의 빈 칸부터 덮어 나가는 것으로 순서를 강제하자.

무식하게 풀 수 있을까?

빈 칸의 수는 50개를 넘지 않으므로 최대 16개 (L 블록 한개는 3칸) 의 블록을 놓는다. 따라서 가능한 답의 상한은 4^16 개가 된다. 완전 탐색으로는 버거운 수의 상한이지만 실제로 각 단계에서 선택 가능한 블록 배치는 크게 제한된다. 예를 들어 빈 칸이 6개 있을 때 이론 상 4^2 가지의 방법이 있지만 실제로는 2가지 방법으로만 배치할 수 있다. 

 

#include <iostream>
#include <vector>
using namespace std;

// L blocks
/*
#   ##  ##   #
##  #    #  ##
*/
const int LBlock[4][3][2] = {
    {{0,0},{1,0},{1,1}},
    {{0,0},{0,1},{1,0}},
    {{0,0},{0,1},{1,1}},
    {{0,0},{1,0},{1,-1}}
};
int H, W;

int boardcover(vector<vector<char>>& board) {
	// 가장 왼쪽 상단에 위치한 빈자리를 찾는다.
    int firstY = -1, firstX = -1;
    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            if (board[y][x] == '.') {
                firstY = y;
                firstX = x;
                break;
            }
        }
        if (firstY != -1) break;
    }
    // 모두 덮힌 한 가지 경우의 의미로 1 반환.
    if (firstY == -1) return 1;

    int ret = 0;

	for (int i = 0; i < 4; ++i) {
        bool isCoverable = true;
        for (int j = 0; j < 3; ++j) {
            // (y[j], x[j]): coordinate for L blocks.
            int y[j] = firstY + LBlock[i][j][0];
            int x[j] = firstX + LBlock[i][j][1];

			if (y[j] < 0 || H <= y[j] || x[j] < 0 || W <= x[j]) 
                isCoverable = false;
            else if (board[y[j]][x[j]] == '#') 
                isCoverable = false;
        }    
        // 현재 블록은 엎을 수 없으므로 다음 블록을 검사.
        if (isCoverable == false) continue;
        
        for (int j = 0; j < 3; ++j) 
            board[y[j]][x[j]] = '#';
        ret += boardcover(board);
        for (int j = 0; j < 3; ++j) 
            board[y[j]][x[j]] = '.';
    }

    return ret;
}

int main() {
    int C; cin >> C;
    vector<vector<char>> board;
    vector<int> answers;

    while (C-- > 0) {
        cin >> H >> W;

        vector<char> row;
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                char c; cin >> c;
                row.push_back(c);
            }
            board.push_back(row);
            row.clear();
        }
            
        answers.push_back(boardcover(board));    
        board.clear();
    }

    for (auto e: answers) cout << e << " ";

    return 0;
}