알고스팟 문제 풀이 BOARDCOVER

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "BOARDCOVER"에 대한 풀이입니다.

목차

1. 문제 해결 전략
2. 코드 전문

문제 해결 전략

BOARDCOVER 문제 URL은 다음과 같습니다.

 

• BOARDCOVER URL

 

제가 이 문제를 해결하기 위해서 체택한 방법은 "무식하게 풀기"입니다. 결론부터 말씀드리면 이 문제는 다음과 같이 풀 수 있습니다.

 

1. 보드를 좌표 (0, 0) 부터 시작해서 보드 끝 좌표 (W-1, H-1)까지 다음을 반복합니다.
2. 블럭을 넣을 수 있는 좌표 (x, y)를 찾습니다.
3. (x, y)에 L자 블럭을 넣을 수 있으면 넣습니다.
4. 계속 채워나가다, 좌표 끝에 도달했을 때, 보드판을 모두 채웠으면, 그 개수를 셉니다.

 

사실 이렇게 해결책을 제시해도 말이 쉽지 우리가 바로 알고리즘 문제를 풀기는 어렵습니다. 어렵다고 포기하지 말고 문제를 여러 조각으로 나누어서 풀어봅시다. 제가 이 문제를 풀기 위해서 나눈 조각은 다음과 같습니다.

 

1. L자 블럭을 놓을 좌표 찾기
2. L자 블럭 표현하기
3. L자 블럭 보드에 놓기
4. 1-3 조각들을 이용해서 끝 좌표에 도달하기

L자 블럭을 놓을 좌표 찾기

먼저 제일 쉬운 조각인 L자 블럭을 놓을 좌표를 만들어봅시다. L자 블럭을 놓을 좌표는 다음 조건만 만족하면 됩니다.

 

1. 해당 좌표에 블럭이 없어야 한다.

그러니까 보드 판 board 상에서 좌표 (x, y) 즉, board[y][x]의 값이 '#'이 아닌 '.'인 값을 찾으면 됩니다. 결국, L자 블럭을 놓을 좌표는 보드 상에서 '.' 값이 있는 좌표 (x, y)를 반환하면 됩니다. 만약 보드상에서 블럭을 놓을 좌표가 없다면, 그러니까 보드가 꽉 차 있을 때, (-1, -1)을 반환하면 됩니다. 이 좌표를 찾기 위한 코드는 다음과 같습니다.

 

pair<int, int> findCoordinate(int H, int W, vector< vector<char>> board) {
    for (int y=0; y<H; y++) {
        for (int x=0; x<W; x++) {
            if (board[y][x] == '.') {
                return make_pair(x, y);
            }
        }
    }

    return make_pair(-1, -1);
}

 

L자 블럭 표현하기

이제 코드 상으로 L자 블럭을 표현해봅시다. 먼저 문제의 조건에 따라서, 다음의 4가지 방식으로 게임판에 L자 블록을 놓을 수 있습니다.

여기서 중요한 점은 '*' 자 표시된 곳이 좌표의 중심이라는 것입니다. 이 L자 블록의 상태를 표시한 것이 다음 코드입니다.

 

const vector<pair<int, int>> TYPES[4] = {
    { make_pair(0, 0), make_pair(1, 0), make_pair(0, 1) },  
    { make_pair(0, 0), make_pair(1, 0), make_pair(1, 1) },  
    { make_pair(0, 0), make_pair(0, 1), make_pair(1, 1) }, 
    { make_pair(0, 0), make_pair(0, 1), make_pair(-1, 1) }  
};

 

여기서 TYPES는 상태 4개를 표현하는 배열이며, TYPES의 원소 하나는 좌표 (x, y)를 기준으로 L자를 표현하기 위한 좌표의 차이 값입니다. 즉 TYPES 원소 하나에 저장되어 있는 각 좌표쌍은 추후에 다음 수식을 표현하기 위한 일종의 코드 기법입니다.

 

"(nx, ny) = (x + pair.first, y + pair.second)"

 

다음 그림을 살펴보시면 이해가 되실겁니다.

L자 블럭 보드에 놓기

이제 보드에 블럭을 놓아봅시다. 보드에 L자 블럭을 넣기 위해서는 다음의 조건들을 먼저 검사해야 합니다.

 

1. L자 블럭을 표시하는 좌표들 (x1, y1), (x2, y2), (x3, y3)가 보드 안에 존재해야 합니다.
2. L자 블럭을 표시하는 좌표들 (x1, y1), (x2, y2), (x3, y3) 중 어느 좌표도 블럭이 놓여있으면 안됩니다.

 

해당 좌표가 보드 상에 존재하는지 검사하려면, 문제의 입력에서 가로를 나타내는 W, 높이를 나타내는 H, 좌표 (x, y)에 대해서 다음의 조건을 검사하면 됩니다.

 

"0 <= x < W && 0<= y < H"

 

이를 코드로 표현하면 다음과 같습니다.

 

bool isRange(int H, int W, int x, int y) {
    return  (0 <= y && y < H) && (0<= x && x < W);
}

 

그 후, 보드판을 나타내는 board의 좌표 (x, y)에서 L자 블럭의 상태에 따라서, 블럭을 놓을 수 있는지 검사하는 코드는 다음과 같습니다.

 

bool isAvailable(int H, int W, vector< vector<char>> board, int x, int y, int state) {
    for (auto move : TYPES[state]) {
        int nx = x + move.first;
        int ny = y + move.second;

        if (!isRange(H, W, nx, ny)) {
            return false;
        }

        if (board[ny][nx] == '#') {
            return false;
        }
    }

    return true;
}

 

그리고 보드판에, (x, y) 좌표와 L자 블럭 상태에 따라서 블럭을 놓고 빼는 과정을 표현한 코드는 다음과 같습니다.

 

void setBoard(vector< vector<char>> &board, int x, int y, int state, char c) {
    for (auto move : TYPES[state]) {
        int nx = x + move.first;
        int ny = y + move.second;
        board[ny][nx] = c;
    }
}

 

블럭을 놓으려면 입력 c에 '#' 값을, 빼려면 '.'를 넣어주면 됩니다. 그리고 setBoard 함수를 사용하기 전에 isAvailable 함수를 호출해서, 이 좌표에 대해서 L자 블럭을 놓을 수 있는지 없는지 먼저 검사해야 한다는 것을 기억하시면 됩니다.

1-3 조각들을 이용해서 끝 좌표에 도달하기

이제 문제를 풀기 위한 모든 조각을 다 갖추었습니다. 이제 좌표 (0, 0)부터 시작해서 끝 좌표 (W-1, H-1)까지 조각들을 이용해서 반복하면 됩니다. 만약 (x, y)에 대해서 L자 블럭을 놓는다고 가정해봅시다. 그럼 다음 그림에서는 4가지 상황이 나타납니다.

첫 번째 상황입니다.

두 번째 상황입니다.

세 번째 상황입니다.

네 번째 상황입니다.

네 번째 상황이러면, 블록을 놓을 수 없습니다. 이제 첫 번째 상황을 선택했을 때를 살펴보도록 하죠.

또 다음의 4가지 상황으로 L자 블럭을 놓을 수 있겠지요. 첫 번째 상황입니다.

두 번째 상황입니다.

세 번째 상황입니다.

네 번째 상황입니다.

결국 이 과정을 반복해서, 끝 좌표까지 도달하면 됩니다. 이 과정을 반복했을 때, 만약 다음 상황이 나타났다고 가정해보죠.

위 경우에서는 딱 한가지 경우의 수만 블럭을 놓아 보드판을 모두 채울 수 있습니다.

이 때 그 다음 상황에서 모든 보드가 채워졌기 때문에, 개수를 세게 됩니다. 이제 다시 블럭을 놓기 전 상황을 돌아가 3가지 상황을 살펴봅시다.

 

위의 경우를 제외한 첫 번째 상황입니다.

위의 경우를 제외한 두 번째 상황입니다.

위의 경우를 제외한 세 번째 상황입니다.

안타깝게도 그 어떤 상황도 놓을 수 없습니다. 이 때는 0을 반환하면 됩니다. 이것을 반복문으로 어떻게 표현할 수 있을까요? 물론 있겠지만 굉장히 어렵습니다. 저는 못하겠습니다!! 다만 우리가 알 수 있는 것은 문제를 해결하기 위해 우리가 알아야 할 입력은 정해져 있다는 것입니다. 이것이 바로 이 문제를 쉽게 해결할 포인트입니다.

 

문제에서 입력은 세로 H, 가로 W, 블럭이 놓여져 있는 상태를 나타내는 보드판 board입니다. 이것들을 가지고 지지고 볶고 하면 됩니다. 즉, 재귀 함수로 이를 표현할 수 있습니다. 결국 다음 과정으로 문제를 해결할 수 있습니다.

 

1. 블럭을 놓을 수 있는 좌표 (x, y)를 찾습니다.
2. (x, y)에 L자 블럭을 넣을 수 있으면 넣습니다. 이 때 4가지 상태에 대해서 다음을 반복합니다.
3. 4가지 블럭 상태에 대해서 블럭을 넣었을 때, 1-2번을 반복합니다.
4. 이를 반복하다 모두 채워졌을 경우, 즉 놓을 수 있는 좌표가 (-1, -1)일 때 개수를 셉니다.

 

이를 코드로 표현하면 다음과 같습니다.

 

int solution(int H, int W, vector< vector<char>> board) {
    auto coordinate = findCoordinate(H, W, board);
    int x = coordinate.first;
    int y = coordinate.second;

    if (y == -1) {    
        return 1;
    }

    int answer = 0;

    for (int i=0; i<4; i++) {
        if ( isAvailable(H, W, board, x , y, i) ) {
            setBoard(board, x, y, i, '#');
            answer += solution(H, W, board);
            setBoard(board, x, y, i, '.');
        }
    }
    
    return answer;
} 

 

재귀 함수 중, 중요한 것은 answer = 0 부터 시작하는 것입니다. 만약 L자 블록의 모든 상태의 경우의 수를 돌았을 때, 반환되는 것이 없을 때 이 0을 반환하게 하는 것입니다. 코드가 잘 이해가 안된다면, answer 를 반환하기 전에, 다음 코드를 추가해주세요. 그럼 어느정도 이해가 되실 겁니다.

 

cout << "(" << x << ", " << y << "), " << anser << endl;

코드 전문

다음은 알고리즘 풀이 코드 전문입니다. main은 입력에 대해서 예외 처리를 한 후 solution 함수를 부릅니다. 문제 입력을 만드는데 코드를 유의깊게 봐주세요.

 

#include <iostream>
#include <vector>

using namespace std;

const vector<pair<int, int>> TYPES[4] = {
    { make_pair(0, 0), make_pair(1, 0), make_pair(0, 1) },  
    { make_pair(0, 0), make_pair(1, 0), make_pair(1, 1) },  
    { make_pair(0, 0), make_pair(0, 1), make_pair(1, 1) }, 
    { make_pair(0, 0), make_pair(0, 1), make_pair(-1, 1) }  
};

bool isRange(int H, int W, int x, int y) {
    return  (0 <= y && y < H) && (0<= x && x < W);
}

pair<int, int> findCoordinate(int H, int W, vector< vector<char>> board) {
    for (int y=0; y<H; y++) {
        for (int x=0; x<W; x++) {
            if (board[y][x] == '.') {
                return make_pair(x, y);
            }
        }
    }

    return make_pair(-1, -1);
}

bool isAvailable(int H, int W, vector< vector<char>> board, int x, int y, int state) {
    for (auto move : TYPES[state]) {
        int nx = x + move.first;
        int ny = y + move.second;

        if (!isRange(H, W, nx, ny)) {
            return false;
        }

        if (board[ny][nx] == '#') {
            return false;
        }
    }

    return true;
}

void setBoard(vector< vector<char>> &board, int x, int y, int state, char c) {
    for (auto move : TYPES[state]) {
        int nx = x + move.first;
        int ny = y + move.second;
        board[ny][nx] = c;
    }
}

int solution(int H, int W, vector< vector<char>> board) {
    auto coordinate = findCoordinate(H, W, board);
    int x = coordinate.first;
    int y = coordinate.second;

    if (y == -1) {    
        return 1;
    }

    int answer = 0;

    for (int i=0; i<4; i++) {
        if ( isAvailable(H, W, board, x , y, i) ) {
            setBoard(board, x, y, i, '#');
            answer += solution(H, W, board);
            setBoard(board, x, y, i, '.');
        }
    }
    
    return answer;
} 

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

    if ( !(1 <= C && C <= 30) ) {
        cout << "fail" << endl;
        return 0;
    }

    for (int i=0; i<C; i++) {
        int H, W;
        cin >> H >> W;

        if (!(1 <= H && H <= 20) || !(1 <= W && W <= 20)) {
            cout << "fail" << endl;
            return 0;
        }

        auto board = vector< vector<char>>(H, vector<char>(W, '.'));
        int cnt = 0;

        for (int y=0; y<H; y++) {
            for (int x=0; x<W; x++) {
                char c;
                cin >> c;
                board[y][x] = c;

                if ( !(c == '#' || c == '.') ) {
                    cout << "fail" << endl;
                    return 0;
                }

                if (c == '.') {
                    cnt += 1;
                }
            }
        }

        if ( cnt > 50 ) {
            cout << "fail" << endl;
            return 0;
        }

        int result = solution(H, W, board);
        cout << result << endl;
    }

    return 0;
}

 

다음 코드를 제출하면, 8ms 이내로 무난하게 통과하는 것을 확인할 수 있습니다.