알고스팟 알고리즘: BOARDCOVER [C++]

문제 출처: https://algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

1. 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

//게임판을 채울 수 있는 도형의 네 가지 모습
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}}
};

//게임판의 x,y 위치에서
//delta가 1이면 게임판을 type번 도형 모습으로 덮는다
//delta가 -1이면 게임판의 type번 도형을 없앤다
bool set(vector<vector<int>>& board, int y, int x, int type, int delta) {
    bool ok = true;
    for (int i = 0; i < 3; i++) {
        //x,y를 기준으로 type번째 도형의 모습
        int ny = y + coverType[type][i][0];
        int nx = x + coverType[type][i][1];
        //도형이 게임판 밖으로 나가거나 다른 도형과 겹치는지 확인
        if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size())
            ok = false;
        //delta가 -1인 경우
        else if ((board[ny][nx] += delta) > 1)
            ok = false;
    }
    return ok;
}

int cover(vector<vector<int>>& board) {
    int y = -1;
    int 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;
    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;
}

int main() 
{
    int C;
    cin >> C;

    while (C--) 
    {
        int y, x;
        cin >> y >> x;
        vector<vector<int>> board(y, vector<int>(x, 0));
        string input;

        for (int i = 0; i < y; i++) 
        {
            cin >> input;
            for (int j = 0; j < input.length(); j++) 
            {
                if (input[j] == '#')
                    board[i][j] = 1;
            }
        }
        cout << cover(board) << endl;
    }
}

(실행)

2. 풀이

재귀 함수를 이용해서 문제를 해결합니다.

int y, x;
cin >> y >> x;
vector<vector<int>> board(y, vector<int>(x, 0));
string input;

for (int i = 0; i < y; i++) 
{
    cin >> input;
    for (int j = 0; j < input.length(); j++)
    {
    	if (input[j] == '#')
            board[i][j] = 1;
    }
}
cout << cover(board) << endl;

board를 0으로 초기화시킨 상태로 선언해주고 입력한 글에 #인 부분이 있다면 해당하는 board 위치에 1로 표시해줍니다. 그리고 cover 함수(재귀)를 호출하여 결과를 출력합니다.

int y = -1;
int 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;

y와 x의 값을 -1로 초기화를 시킨 뒤 반복문을 통해서 board의 흰 칸(0인 부분)을 찾는다면 x와 y의 값을 해당하는 위치 값으로 초기화를 해주는데 만약 y와 x가 -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;

set 함수를 통해서 미리 예상한 도형의 모양으로 보드판이 덮어지는지 안되는지 확인 작업 후 덮어진다면 ret에 cover 함수의 결과를 추가로 저장해준다. 그리고 덮었던 블록을 지워준다. 왜냐하면 다른 경우의 수를 확인할 때 덮어있다고 한다면 탐색하기가 어렵기 때문이다. 그리고 이 모든 재귀 함수의 과정이 종료되면 ret에 저장된 값을 결과로써 출력하면 된다.

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}}
};

bool set(vector<vector<int>>& board, int y, int x, int type, int delta) {
    bool ok = true;
    for (int i = 0; i < 3; i++) {
        //x,y를 기준으로 type번째 도형의 모습
        int ny = y + coverType[type][i][0];
        int nx = x + coverType[type][i][1];
        //도형이 게임판 밖으로 나가거나 다른 도형과 겹치는지 확인
        if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size())
            ok = false;
        //delta가 -1인 경우
        else if ((board[ny][nx] += delta) > 1)
            ok = false;
    }
    return ok;
}

set 함수는 미리 예상한 도형의 모양으로 보드판을 덮을 수 있는지 확인해주며 동시에 덮은 보드를 다시 벗기는 작업을 하는 함수이다. delta의 값이 1이라면 보드판을 덮지만 -1이라면 제거한다.

기존의 coverType으로 만들어둔 위치정보로 도형 모양에 해당하는 위치를 확인하고 도형이 게임판 밖으로 나가 지는지 혹은 다른 도형과 겹치는지 확인을 해준다.

3. 느낀 점

접근 방법까지는 비슷하게 접근했으나 문제는 구현부에서 원하는 대로 구현하는 것을 실패하여 책에 있는 코드를 보고 작성하였다. 사실 예전에도 이 문제를 풀려고 시도했는데 그때는 코드조차 이해하기 힘들었는데 지금은 코드에 대해 이해하고 있어서 비록 실패하기는 했지만 조금씩 나아지는 느낌을 받고 있다.