종만북 GAMEBOARD C++ 풀이 (코드제공)

1. 문제 설정 확인

딱히 설명할 정도로 문제설정이 복잡하진 않다. 단순히 배열의 모든 요소를 1로 만들 수 있으면 된다.

2. 문제 풀이

PICNIC과 비슷해보이는 문제다. 일단은 코드부터 보자.

3. 해답 코드

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

const 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 x, int y, int i, int j){
    bool ok = true;
    for(int k = 0; k < 3; ++k){
        const int nx = x + coverType[i][k][0];
        const int ny = y + coverType[i][k][1];
        if(nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size())
            ok = false;
        else {
            board[nx][ny] += j;
            if(board[nx][ny] > 1) ok = false;
        }
    }
    return ok;
}

int solution(vector<vector<int>> &board, int width, int height){
    int minX = -1;
    int minY;
    for(int i =0; i < height; i++){
        for (int j =0; j< width; j++){
            if (board[i][j] == 0){
                minX = i;
                minY = j;
                break;
            }
        }
        if(minX != -1) break;
    }
    if (minX == -1) return 1;
    int result = 0;
    for (int z =0; z < 4; z++) {
        if(set(board, minX, minY, z, 1)){
            result += solution(board, width, height);
        }
        set(board, minX, minY, z, -1);
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    char a = '#';
    for(int i = 0; i < n; i++){
        int height, width;
        cin >> height >> width;
        vector<vector<int>> board;
        for(int k = 0; k < height; k++) {
            string str;
            vector<int> line(0);
            cin >> str;
            for (int j = 0; j < width; j++) {
                if (str[j] == a) line.push_back(1);
                else line.push_back(0);
            }
            board.push_back(line);
        }
        cout << solution(board, width, height) << endl;
    }
}

코드 설명

보시다시피, 기본적으로는 백트래킹의 형식을 취한다. 사실 크게 어려운 건 없었다. 기본적인 백트래킹의 형식인

조건에 따라 방문처리를 하고
방문처리를 하게될 시 재귀함수를 사용해 안으로 들어가며
모든 재귀함수의 호출이 끝나고 최상단으로 돌아올 시 방문처리를 해제한다.

를 취한다. 다만, 무작정 저렇게 구현했다간, 저번 포스트인 PICNIC처럼, 블럭 놓는 순서를 다 구분하게 되다보니, 가장 왼쪽 위부터 블럭을 놓는 것이 필요하고, 그것이 minX minY의 사용 이유이다.

또 tricky한 점이, 바로 set함수이다. set 함수는

방문처리가 가능한지의 여부를 반환해준다.
실제로 함수 내에서 방문처리를 해준다.

즉, 방문처리를 하되, 이미 방문한 적이 있는 칸이거나 방문을 할 수 없는 칸이라면 false를 리턴해 재귀호출을 막고 바로 방문해제 함수로 들어가게 해주는 함수다. 매개변수 j에 1이나 -1이 오는데, 왜 단순히 board[mx][my] = 1, board[mx][my] = 0을 쓰는것이 아닌 +=를 쓰는지 한 번 생각해보자. 1 0 0 이라는 세 칸을 방문한다면, 모두 1로 동일하게 방문처리를 하면 1 1 1이 된다. 물론 1 0 0에서 이미 1이 있었으니, ok는 false가 될 것이고, 원 함수의 if문을 빠져나가 방문해제 처리를 할 것이다. 그럼 당연하게도, 원래 있던 1 0 0의 1까지 모두 방문해제 처리되어 0 0 0 이 되어버린다, 즉, 무한루프에 빠진다. 따라서 += 1 을 해주어 2 1 1을 만들어주고, 나중에 += -1 을 해주어 1 0 0을 만들어주면 된다.

기억하자, 백트래킹에서 방문처리했던 모든 칸은, 그 방문한 횟수만큼 다시 방문해 방문해제를 거칠 수 밖에 없다

왜냐하면, 결국 백트래킹의 모든 호출이 끝난 후의 board는 결국 초기 상태 그대로이기 때문이다.

솔직히 set 함수만 아니면 30분정도 걸렸을 문제인데, set함수에서 계속 오류가 나서 결국 이 한 문제 푸는데 한시간이 넘게 걸려버렸다 (…) 결국 책의 도움을 받아보니, 부호 하나 잘못써서 계속 오류 나던 것이어서, 더욱 현타가 온다… ㅎㅎ…

Source

종만북, 2022.07.22
CLion