[종만북] - 게임판 덮기(완전탐색)

문제

접근방법

재귀함수를 이용한 완점탐색이다.

 

순서를 강제하여 중복으로 세는 문제를 해결한다.

코드

#include <iostream>
#include <vector>

#define FOR(i,n) for (int i=0;i<(n);++i) 
using namespace std;

//주어진 칸을 덮을 수 있는 네가지 방법
//블록을 구성하는 세 칸의 상대적 위치 (dy, dx)의 목록
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}}
};
int C, h, w;
vector<vector<int> > board;

bool set(vector<vector<int> >& board, int y, int x, int type, int delta);
//board의 (y, x)를 type번 방법응로 덮거나, 덮었던 블록을 없앤다.
//delta = 1이면 덮고, -1이면 덮었던 블록을 없앤다.
//만약 블록이 제대로 덮이지 않은 경우(게임판 박으로 나가거나, 곂치거나, 검은 칸을 덮을 때) false를 반환한다.
int cover(vector<vector<int> >& board);

int main() {
    cin >> C;
    while (C--) {
        int cnt = 0;
        int answer = 0;
        cin >> h >> w;
        board = vector<vector<int> >(h, vector<int>(w, 0));
        FOR(i,h) FOR(j,w) {
            char temp;
            cin >> temp;
            if (temp == '#') board[i][j] = 1;
            else {
                board[i][j] = 0;
                cnt++;
            }
        }
        if (cnt == 0) answer = 1;
        else if (cnt % 3 == 0) answer = cover(board);
        cout << answer << '\n';
    }
}

bool set(vector<vector<int> >& board, int y, int x, int type, int 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;
}

//board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다.
//board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
//board[i][j] = 0 아직 덮이지 않은 칸
int cover(vector<vector<int> >& board) {
    //아직 채우지 못한 칸 중 가장 윗 줄 왼쪽에 있는 칸을 찾는다.
    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;
    }
    //기저 사례: 모든 칸을 채웠으면 1을 반환한다.
    if (y == -1) return 1;
    int ret = 0;
    for (int type=0;type < 4;++type) {
        //만약 board[y][x]를 type형태롤 덮을 수 있으면 재귀호출한다.
        if (set(board, y, x, type, 1)) 
            ret += cover(board);
        //덮었던 블록을 채운다.
        set(board, y, x, type, -1);
    }
    return ret;
}

개선할 점

빈칸에 도달했을 때, 그 빈칸의 위치를 기준으로 색칠해야할 칸의 인덱스를 저장하는 것이 인상깊다.

 

예를 들어,

도착한 빈칸을(0,0)으로 뒀을 때, 오른 쪽 칸은 (0,1), 아래 칸은 (1, 0), 왼쪽 대각선 칸은 (1, -1)이다.

 

재귀함수를 이용해 복잡해 보이는 완전탐색을 풀어낼 수 있었다.