[종만북] [6장 무식하게 풀기] 6.5장 게임판 덮기

상당히 교훈적인 문제이다.

 

이 문제는 입력 숫자가 작은 편이므로 Bruteforce 방법을 먼저 생각하는 것이 압도적으로 유리하다.

다만, 이 문제를 풀 때 가장 애를 먹은 사항이 중복되지 않으면서 채워나가는 것이다.

앞의 6.2장 피크닉 문제에서의 교훈인 "중복을 피하기 위해서 가장 좋은 방법이 가장 왼쪽 상단 index를 기준으로 하는 것이다"을 활용하여 조금씩 채워나가면 된다.

 

기본적인 문제 풀이의 방향성은 다음과 같다.

1. 비어있는 가장 왼쪽 상단 cordinate를 찾는다.
2. 해당 cordinate를 덮을 수 있는 블록을 찾는다.(이 과정에서 블록이 외부로 넘어가는지 여부를 체크한다.)
3. 해당 블록을 덮었다고 가정하고 이후의 과정을 반복한다. 
(재귀를 활용해서 이를 구현하되, 각 단계가 끝날 때는 반드시 덮은 블록을 제거해야 한다.)

만약, 가장 왼쪽 상단을 덮을 수 있는 블록 배치가 존재하지 않는다면
만족하는 방향성으로는 전체를 덮을 수 없다는 의미이다.
(이 내용은 귀류법으로 증명하면 된다. 해당 배치에서 왼쪽을 덮을 수 없다면 전체를 어떠한 방법으로도 전부 다 채울 수 없다는 의미이기 때문이다.)

다만, 처음에 계산할 때 빈 영역이 3의 배수가 아닌 경우에는

볼 필요도 없이 다 채울 수 없으므로 먼저 처리해 준다.

 

위의 코드를 구현한 결과는 다음과 같다.

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

using namespace std;

int height, width;
int calculated_result;
int check_store[4][3][2] = {
    {{0, 0}, {0, 1}, {1, 1}},
    {{0, 0}, {1, 0}, {1, 1}},
    {{0, 0}, {0, 1}, {1, 0}},
    {{0, 0}, {1, 0}, {1, -1}}
};

// 블럭 넣어야하는 갯수 체크
// 3의 배수가 아니면 -1, 3의 배우시면 해당하는 갯수
int pair_count(vector<string> &data_store){
    int result = 0;
    for(int i = 0; i< height; i++){
        for(int j = 0; j < width; j++){
            if(data_store[i][j] == '.') result += 1;
        }
    }
    if(result % 3 != 0) return -1;
    else return result / 3;
}

pair<int, int> find_top_left(vector<string> &data_store){
    for(int i = 0; i < height; i++){
        for(int j = 0; j < width; j++){
            if(data_store[i][j] == '.'){
                return make_pair(i, j);
            }
        }
    }
}

// 비어있으면 1 출럭, 범위 밗이거나 차있으면 0 출력
int blank_check(int x, int y, vector<string> &data_store){
    if(x < 0 || x >= height || y < 0 || y >= width) return 0;
    else{
        if(data_store[x][y] == '.') return 1;
        else return 0;
    }
}

// 해당 check_value가 유효한 값을 지니는지 체크하는 함수
// 1 이면 유효, 0이면 무효
int case_check(int x, int y, vector<string> &data_store, int check_value){
    for(int i = 0; i < 3; i++){
        int dx = x + check_store[check_value][i][0];
        int dy = y + check_store[check_value][i][1];
        if(blank_check(dx, dy, data_store) == 0) return 0;
    }
    return 1;
}

void make_not_blank(int x, int y, vector<string> &data_store, int check_value){
    for(int i = 0; i< 3; i++){
        int dx = x + check_store[check_value][i][0];
        int dy = y + check_store[check_value][i][1];
        data_store[dx][dy] = '#';
    }
    return;
}

void make_blank(int x, int y, vector<string> &data_store, int check_value){
    for(int i = 0; i< 3; i++){
        int dx = x + check_store[check_value][i][0];
        int dy = y + check_store[check_value][i][1];
        data_store[dx][dy] = '.';
    }
    return;
}

void checker_function(vector<string> &data_store, int pair_num){
    if(pair_num == 0){
        calculated_result += 1;
        return;
    }// 목표하는 값 도달
    else{
        pair<int, int> top_left_cor = find_top_left(data_store);
        int pair_check[4] = {0};
        for(int i = 0; i < 4; i ++){
            pair_check[i] = case_check(top_left_cor.first, top_left_cor.second, data_store, i);
        }
        // 중간에 만족하는 상황이 없는 것
        if(pair_check[0] == 0 && pair_check[1] == 0 && pair_check[2] == 0 && pair_check[3] == 0){
            return;
        } 
        else{
            for(int i = 0; i < 4; i++){
                // 만족하는 케이스일 때
                if(pair_check[i] == 1){
                    make_not_blank(top_left_cor.first, top_left_cor.second, data_store, i);
                    checker_function(data_store, pair_num -1);
                    make_blank(top_left_cor.first, top_left_cor.second, data_store, i);
                }
            }
            return;
        }
    }
}
int main(void){
    int test_case_num;
    cin >> test_case_num;

    for(int i = 0; i < test_case_num; i++){
        cin >> height >> width;
        vector<string> data_store;
        for(int i = 0; i < height; i++){
            string temp;
            cin >> temp;
            data_store.push_back(temp);
        }// data_store

        int pair_num = pair_count(data_store);

        // 만족하는 상황이 아얘 안되는 경우
        if(pair_num == -1){
            cout << "0\n";
            continue;
        }
        else{
            calculated_result = 0;
            checker_function(data_store, pair_num);
            cout << calculated_result << "\n";
        }
    }
    return 0;
}

특히, dy, dx 같이 관계들을 배열로 미리 정리해두고 따로 뽑아서 쓰는 아이디어는 매우 기억할만한다.

(이 부분은 이전 문제인 피크닉 해설을 보면서 학습하였다.)

 

자주 보면서 정리하도록 하자.