[알고리즘 문제] algospot - BOARDCOVER

"프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"을 보다가 문제를 발견했고, 자주 나오는 문제유형이라 생각되어 한번 풀어 보았다.

https://algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

문제는 간단하다, 그냥 제한된 공간에┌─, ─┐,└─, ─┘(1x1도형 3개로 만들어진 도형)을 몇가지 방법으로 딱 맞게 넣을 수 있는지 풀어보는 문제이다.

 

해결 방법은 간단하다. 주어진 도형을 모두 사용사여 모든 경우의 수를 검사하는 방법이다. 개인적으로 책 내용만 봐서는 한번에 이해가 안되었는지, 이 글을 읽고는 한번에 이해가 되게 작성해보도록 노력을...

 

문제의 전체적인 컨셉은 재귀이다.

예를 들어 3중 for문이 있고, 각 for문은 가변변수는 a,b,c이고 이 값은 1~3의 값을 가진다. 세번째 for문에서 a,b,c를 출력하면

1 1 1

1 1 2

1 1 3

1 2 1

1 2 2

1 2 3

1 3 1

1 3 2

 1 3 3

.....

 

마찬가지 방법으로 위의 문제를 풀 수 있다. 각 번호를 도형이라고 생각하면 된다. 위의 번호의 조합(도형의 조합)으로 칸을 모두 메꿀 수 있다면 1가지의 방법을 찾은 것이다. 이 문제는 이런 가지의 방법수가 몇개나 있는지를 출력하는 문제이다.

 

일단 먼저 코드를 보자. 이해만 한다면 엄청 쉽다.

#include <iostream>

using namespace std;

int types[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}} // ─┘

};
int height, width;
int map[20][20];

bool set(int y, int x, int type, int delta) // y,x,위치에서 type 도형(┌─,─┐,└─,─┘)을 놓을 수 있는지 검사
{
    bool ok = true;
    for (int i = 0; i < 3; i++)
    {
        int ny = y + types[type][i][0];
        int nx = x + types[type][i][1];

        if (ny < 0 || ny >= height || nx < 0 || nx >= width) // 도형을 놓는 위치가 배열에서 벗어나는지
        {
            ok = false;
        }
        else if ((map[ny][nx] += delta) > 1) // 도형을 놓는 위치가 벽인지
        {
            ok = false;
        }
    }
    return ok;
}

int cover() // map[h][w]==0인 위치에서 여러 도형을 계속 놓아봄.
{
    int y = -1, x = -1;

    for (int h = 0; h < height; h++)
    {
        for (int w = 0; w < width; w++)
        {
            if (map[h][w] == 0)
            {
                x = w;
                y = h;
                break;
            }
        }
        if (y != -1)
        {
            break;
        }
    }
    if (y == -1) // x==-1이라는 말은, 0이 없다. 즉 모든 칸을 블럭으로 다 채웠다는 의미이기 떄문, 1가지 경우 찾음 !
    {
        return 1;
    }

    int count = 0;

    for (int type = 0; type < 4; type++) // 현재 위치에서 4가지 타입의 도형을 모두 놓아봄.
    {

        if (set(y, x, type, 1))
        {
            count += cover();
        }

        set(y, x, type, -1); // 덮었던 블록을 다시 지운다.
    }

    return count;
}

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

    char text[20];

    for (int i = 0; i < test_case; i++)
    {
        cin >> height >> width;
        for (int h = 0; h < height; h++)
        {
            cin >> text;
            for (int w = 0; w < width; w++)
            {
                map[h][w] = (text[w] == '#') ? 1 : 0;
            }
        }

        cout << cover() << endl;
    }
    return 0;
}

 

 

일단 무슨 함수가 있고, 함수의 역할을 먼저 말해보면,

 

1. cover : 0인 위치에서 여러 도형을 놓는다

2. set : 0인 위치에서 도형을 놓을 수 있는지 검사한다(도형이 배열의 크기에 벗어나는지, 벽에 부딪히지 않는지)

 

 

1. 먼저 cover함수에서 첫번째 하는 일은 배열에서 왼쪽위 -> 오른쪽아래 방향으로 0이 있는 위치를 찾고, 이 위치를 x,y에 저장한다.

 

( 근데, 0을 못찾았다 ? -> 이 경우는 배열의 0이 모두 1로 변한 경우(도형이 모두 메꿔진 경우)이고 이는 도형으로 메꿀 수 있는 1가지의 경우를 찾았다는 말이기 때문에 1을 return )

 

2. 그러면 x,y위치에서 도형을 놓을 수 있는지 검사하자. 어떻게 ? 각 도형이 배열에서 위치를 잡기 위해서는 좌표가 필요하다. 그 좌표는 type에 저장했고 그 도형의 위치가 배열에서 벗어나는지, 도형이 놓일 위치가 벽은 아닌지 검사하는 작업은 set함수에서 한다.

 

3. 여기서, set함수에서 성공여부에 상관없이 도형이 놓일 위치(0으로 표시된 곳)에 1로 체크한다.

도형이 놓여질 수 있다 ? -> 1과정 반복(재귀)

도형을 놓을 수 없다 ? -> set함수에서 1로 체크한 부분을 다시 0으로 체크 (원상복구)

 

코드는 정확히 위의 과정을 반복하면서 돌아간다. 언제까지 ? cover함수에서 0을 발견할 수 없을 떄 까지(x==1이 되는 경우)

이 조건이 재귀함수의 기저조건이 된다.