[C++] Algospot - 게임판 덮기(BOARDCOVER)

www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

<풀이>

1. 보드를 입력받는다.

2. 해당 보드를 제시된 블록들로 채울 수 있는 모든 경우의 수를 출력한다.

 

<해법>

1. 블록을 채우는 방법

=> 보드를 탐색해 나가면서 가장 처음 흰색('.')이 나올 때, 이 부분을 블록으로 채워줘야 합니다. 이 때, 4가지 타입이 가능한 블록들의 좌표를 잘 정리해 두면, 블록으로 채울 때 굉장히 쉬워집니다. 저는 아래와 같이 블록들의 좌표를 구현하였습니다.

 

#include <iostream>
#include <string>
#include <string.h>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
int H, W;
char map[20][20];
int answer;
 
//4개 블록의 좌표
pos block[4][3] = {
    {{0,0}, {0,1}, {1,0}},  //①
    {{0,0}, {1,0}, {1,-1}}, //②
    {{0,0}, {1,0}, {1,1}},  //③
    {{0,0}, {0,1}, {1,1}}   //④
};
 
int countWhite() {
    int count = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '.') {
                count++;
            }
        }
    }
    return count;
}
 
pos firstWhitePos() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '.') {
                return { i, j };
            }
        }
    }
}
 
bool isTypeAble(pos p, int type) {
 
    for (int i = 0; i < 3; i++) {
        int x = p.x + block[type][i].x;
        int y = p.y + block[type][i].y;
 
        if (x < 0 || y < 0 || x >= H || y >= W) {
            return false;
        }
 
        if (map[x][y] == '#') {
            return false;
        }
    }
 
    return true;
 
}
 
void colorBoard(pos p, int type, char color) {
 
    for (int i = 0; i < 3; i++) {
        int x = p.x + block[type][i].x;
        int y = p.y + block[type][i].y;
 
        map[x][y] = color;
    }
 
}
 
void boardCover(int remainCnt) {
    
    //종료 조건 : 블록을 모두 놓은 경우
    if (remainCnt == 0) {
        answer++;
        return;
    }
 
    //칠해할 흰색 부분(가장 첫 번째 등장한 흰색)
    pos cur = firstWhitePos();
 
    //4개의 블록 타입 모두 넣어보기
    for (int type = 0; type < 4; type++) {
 
        //타입을 칠할 수 있다면
        if (isTypeAble(cur, type)) {
            
            //검정색으로 칠하기
            colorBoard(cur, type, '#');
 
            //재귀 호출
            boardCover(remainCnt - 1);
 
            //흰색으로 다시 칠하기
            colorBoard(cur, type, '.');
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        H = 0, W = 0;
        memset(map, '#', sizeof(map));
        answer = 0;
 
        //입력
        cin >> H >> W;
        for (int i = 0; i < H; i++) {
            string tmp;
            cin >> tmp;
            for (int j = 0; j < W; j++) {
                map[i][j] = tmp[j];
            }
        }
 
        //해법
        /*
        모두 검정색으로 채워져 있는 경우 or 흰색 개수 3의 배수 아닌 경우 -> 탐색X
        나머지 경우는 블록을 모두 놓아본다
        */
        if (countWhite() != 0 && countWhite() % 3 == 0) {
            boardCover(countWhite() / 3);
        }
 
        //결과 출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스와 구현에 대해 알아볼 수 있는 문제였습니다.

---

위 문제에서 구현이 어렵다고 생각되시면, 아래 문제를 먼저 풀어보시는 것도 도움이 될 것 같습니다!

www.acmicpc.net/problem/14500

14500번: 테트로미노