[ 프로그래머스 블록 게임 (Lv4) ] (C++)

프로그래머스의 블록 게임 (Lv4) 문제이다.

[ 문제풀이 ]

검은 블록을 떨어뜨려서 없앨 수 있는 블록의 갯수를 구해야 하는 문제이다.

본격적인 구현에 앞서서 우리가 문제를 통해서 알 수 있는 정보 하나를 알아보고 넘어가자.

문제에 주어지는 블록은 총 12가지 모양이 있다.

.

이렇게 12가지 모양이 있는데 우리는 주어진 맵에 랜덤적으로 존재하는 위의 모양들에서 검은 블록을 떨어뜨려서 속이 꽉 채워진 블록을 만들어서 없애야 한다.

그런데 ! 우리는 애초에 12가지 모양에 대해서 생각을 할 필요가 없다. 왜냐하면 ! 사실 위의 12가지 모양 중에서, 이미 생긴 것 자체만으로도 검은 블록으로 속이 꽉 채워진 블록을 만들 수 없는 블록이 대다수이기 때문이다.

예를 들어서 맵에 그 어떤 블록도 없고 1번 블록 하나만 있다고 가정해보자. 과연 검은색 블록을 채울수 있을까 ??

.

1번 도형에서 위의 그림처럼 검은색 블록 2개를 위와 같이 넣어서 채울 수 있을까 ?? 채울수가 없다. 왜 ? 애초에 검은 블록을 떨어뜨릴 때 위쪽에서 한 줄을 정해서 그 줄로만 떨어뜨릴 수 있기 때문이다. 우리가 평소에 즐겨하던 테트리스처럼 이 줄 저 줄 왔다갔다 하면서 채울 수 있는 블록이 아니다. 그럼, 1번 블록을 위의 그림처럼 검은색 블록을 채우기 위해서는 다음과 같이 검은 블록이 떨어져야 한다는 것이다.

.

즉 위와 같은 형태로 검은블록을 떨어뜨려야 한다는 이야기인데, 딱 봐도 알겠지만 위의 그림처럼 검은 블록을 떨어뜨리게 되면 1번 도형 위에 검은 블록이 쌓이게 되지, 절대로 1번 도형을 꽉 채운 도형으로 만들 수는 없다.

이렇게, 위에서 예를 들어서 이야기한 '1번 도형'처럼 애초에 생긴 것 자체만으로도 절대로 꽉 채운 블록을 만들 수 없는 도형들이 많이 있다.

.

다시 한번 그림을 가져와봤다. 그럼, 생긴 것 만으로 검은 블록을 통해서 꽉 채운 도형으로 만들지 못하는 도형들이 뭐가 있을지 찾아보자. 바로 [ 1 , 2 , 5 , 8 , 10 , 11 , 12 ] 이다. 이 7개의 도형들은 다른 도형이 어떻게 있든 없든 상관없이, 그 도형 자체만으로도 검은블록을 통해서 없앨 수 있는 도형들이 아니다.

즉 ! 우리가 고려해야 할 도형은 딱 5가지 뿐이라는 것이다. [ 3 , 4 , 6 , 7 , 9 ]

이렇게 5가지 도형에 대해서만 판단을 해주면 된다. 본인은 "하나의 점을 기준으로, 우리가 고려해야 할 도형인지 판단" 해주었다.

.

위에 5가지 도형들에 찍어놓은 초록색 점은 본인이 선정한 기준점들이다.

먼저 3번 도형 같은 경우를 보자.

3번 도형같은 경우는 초록색 점을 기준으로 'ㄴ' 모양의 형태를 가지고 있다.

이를 좌표로 나타내보자. 초록색 점을 (x , y) 라고 가정해보자.

(본인은 세로를 x , 가로를 y 로 잡고 계산합니다. 즉, (0, 0)에서 아래쪽으로 한칸 움직이게 되면 (1, 0)이 됩니다. )

초록색점을 (x , y)로 두게 된다면, 3번 도형을 이루는 4개의 좌표를 표현해보면 다음과 같다.

{ (x , y) , (x + 1 , y) , (x + 1 , y + 1) , (x + 1 , y + 2) }

4번도형은 { (x , y) , (x + 1 , y) , (x + 2 , y) , (x + 2 , y - 1) }

6번도형은 { (x , y) , (x + 1 , y) , (x + 2 , y) , (x + 2 , y + 1) }

7번도형은 { (x , y) , (x + 1 , y) , (x + 1 , y - 1) , (x + 1 , y - 2) }

9번도형은 { (x , y) , (x + 1 , y - 1) , (x + 1 , y) , (x + 1 , y + 1) } 이 된다.

위와 같은 관계식을 dx[][], dy[][] 라는 2차원 배열 2개를 이용해서 나타내주었다.

dx[5][6], dy[5][6] 의 크기로 2개의 2차원 배열을 선언해주었다.

먼저 dx[5][6] 에서 '5'의 의미는 총 5개의 도형을 의미한다. 우리가 고려해야 할 도형은 5개 뿐이기 때문에 '5'로 설정해주었다.

0번 = 3번, 1번 = 4번, 2번 = 6번, 3번 = 7번, 4번 = 9번 도형을 의미하는 것이다.

'6'의 의미는 6개의 칸을 의미한다. 각 도형을 이루고 있는 칸의 갯수는 4칸이다. 그런데 왜 6칸일까 ??

바로 "각 도형을 이루고 있는 칸의 갯수 4칸 + 검은색 블록 2개를 떨어뜨려야 하는 칸의 갯수 2칸"을 해서 총 6칸이 되는 것이다.

void Setting()
{
    dx[0][0] = 0; dx[0][1] = 1; dx[0][2] = 1; dx[0][3] = 1; dx[0][4] = 0; dx[0][5] = 0;
    dy[0][0] = 0; dy[0][1] = 0; dy[0][2] = 1; dy[0][3] = 2; dy[0][4] = 1; dy[0][5] = 2;
    dx[1][0] = 0; dx[1][1] = 1; dx[1][2] = 2; dx[1][3] = 2; dx[1][4] = 0; dx[1][5] = 1;
    dy[1][0] = 0; dy[1][1] = 0; dy[1][2] = 0; dy[1][3] = -1; dy[1][4] = -1; dy[1][5] = -1;
    dx[2][0] = 0; dx[2][1] = 1; dx[2][2] = 2; dx[2][3] = 2; dx[2][4] = 0; dx[2][5] = 1;
    dy[2][0] = 0; dy[2][1] = 0; dy[2][2] = 0; dy[2][3] = 1; dy[2][4] = 1; dy[2][5] = 1;
    dx[3][0] = 0; dx[3][1] = 1; dx[3][2] = 1; dx[3][3] = 1; dx[3][4] = 0; dx[3][5] = 0;
    dy[3][0] = 0; dy[3][1] = 0; dy[3][2] = -1; dy[3][3] = -2; dy[3][4] = -1; dy[3][5] = -2;
    dx[4][0] = 0; dx[4][1] = dx[4][2] = dx[4][3] = 1; dx[4][4] = 0; dx[4][5] = 0;
    dy[4][0] = 0; dy[4][1] = -1; dy[4][2] = 0; dy[4][3] = 1; dy[4][4] = -1; dy[4][5] = 1;
}

이렇게 먼저 세팅을 다 해주었는데, 간단하게 3번 4번 line에 대해서만 이야기하겠다.

dx[0][] 과 dy[0][]의 값들을 설정해놓은 라인이 3, 4번 line인데, 이는 0번 도형을 의미한다. 즉, 0번 도형은 우리가 위에서 그림으로 봤을 때 '3'번도형을 의미한다.

3번 도형을 채우기 위해서는 { (x , y) , (x + 1 , y) , (x + 1 , y + 1) , (x + 1 , y + 2) } 이렇게 4개의 좌표가 하나의 도형이 되어야 한다.

이 4개의 좌표를 x와 y를 따로보게되면, { x , x + 1 , x + 1 , x + 1 } , { y , y , y + 1, y + 2 } 가 된다.

3번,4번라인에서 dx[0]([0][1][2][3]) 과 dy[0]([0][1][2][3]) 을 보게되면 위의 식을 표현해 놓은 것이다.

그리고 dx[0][4] , dx[0][5] , dy[0][4], dy[0][5] 를 보게되면 "검은색 칸을 채워야 하는 2칸"을 의미한다. 그 칸들을 적어놓은 것이다.

이제 위와 같이 세팅 작업을 모두 진행했다면, 모든 맵의 좌표를 순차적으로 탐색하면서 0이 아닌 좌표가 나온다면

1. 지울 수 있는 도형인지 (우리가 말했었던 3, 4, 6, 7, 9번 도형 중 하나인지) 판단해주고

2. 지울 수 있는 도형이라면 검은색 블록을 떨어뜨릴 수 있는지 판단해주면된다.

지울 수 있는 도형이라고 무조건 지울 수 있는 것이 아니다. 검은색 도형을 떨어뜨렸을 때, 그 칸수를 채울 수 있는지 판단해 주어야 한다. 검은색 도형으로 그 빈 칸을 채울 수 있는지는, 해당 열에서 0번 행까지 역으로 올라가면서 또 다른 블록이 없는지 체크해 주면 된다.

마지막으로 ! 우리가 생각해 줘야 할 한가지 부분에 대해서 더 알아보자.

.

이와 같은 형태로 존재한다고 생각해보자. 우리는 이 경우에는 '2번 도형'을 먼저 없앤 후에, '1번 도형'을 없애버리면 2개의 블록을 모두 없애버릴 수 있다.

그런데 ! 모든 맵을 (0 , 0) 좌표부터 순서대로 도는 경우를 생각해보자.

그럼 (1, 0)에 존재하는 1번 도형의 기준점을 먼저 방문할 것이다. 그런데, 1번 도형을 판단할 때에는, 1번 도형은 지울 수 있는 도형이지만, 2번 도형이 검은색 블록이 채워져야 할 칸을 막고 있기 때문에 검은색 블록을 채울 수 없다 ! 따라서 지울 수 없는 도형이다 ! 라고 판단하고 넘어가게 될 것이다.

그리고나서는 (1, 2)에서 '2'번도형의 기준점을 방문해서 2번 도형을 지우게 될 것이다. 그리고 나서 (2, 0)에서 방문하는 1번 도형은 우리가 생각했던 기준점이 아니기 때문에, 당연히 올바르지 않은 도형이라 판단하게 될 것이다.

즉 ! 1번도형은 2번도형을 먼저 지운 후에, 지워버릴 수도 있는데 못 지우는 걸로 잘못 판단되는 경우가 존재할 수 있다.

따라서 ! 이런 경우를 대비해서, "하나의 도형이 삭제되면, y좌표를 반드시 0으로 초기화"를 시켜주어야 한다.

이렇게 되면, 2번 도형을 지우고 나서도 (1, 2)에서 (1, 3)이 아닌 다시 (1, 0)을 방문하게 될 것이다. 그럼 다시 1번 도형을 제대로 된 기준점에서 판단하게 될 것이고 지울 수 있다 판단해서 지우게 될 것이다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
int N;
int dx[5][6], dy[5][6];
bool Visit[205];
 
void Setting()
{
    /* 기초 세팅 작업 */
    dx[0][0] = 0; dx[0][1] = 1; dx[0][2] = 1; dx[0][3] = 1; dx[0][4] = 0; dx[0][5] = 0;
    dy[0][0] = 0; dy[0][1] = 0; dy[0][2] = 1; dy[0][3] = 2; dy[0][4] = 1; dy[0][5] = 2;
    dx[1][0] = 0; dx[1][1] = 1; dx[1][2] = 2; dx[1][3] = 2; dx[1][4] = 0; dx[1][5] = 1;
    dy[1][0] = 0; dy[1][1] = 0; dy[1][2] = 0; dy[1][3] = -1; dy[1][4] = -1; dy[1][5] = -1;
    dx[2][0] = 0; dx[2][1] = 1; dx[2][2] = 2; dx[2][3] = 2; dx[2][4] = 0; dx[2][5] = 1;
    dy[2][0] = 0; dy[2][1] = 0; dy[2][2] = 0; dy[2][3] = 1; dy[2][4] = 1; dy[2][5] = 1;
    dx[3][0] = 0; dx[3][1] = 1; dx[3][2] = 1; dx[3][3] = 1; dx[3][4] = 0; dx[3][5] = 0;
    dy[3][0] = 0; dy[3][1] = 0; dy[3][2] = -1; dy[3][3] = -2; dy[3][4] = -1; dy[3][5] = -2;
    dx[4][0] = 0; dx[4][1] = dx[4][2] = dx[4][3] = 1; dx[4][4] = 0; dx[4][5] = 0;
    dy[4][0] = 0; dy[4][1] = -1; dy[4][2] = 0; dy[4][3] = 1; dy[4][4] = -1; dy[4][5] = 1;
}
 
int Check(int x, int y, vector<vector<int>> board)
{
    /* 해당 도형을 지울 수 있는 도형인지 판단하는 함수. */
    int Value = board[x][y];
    for (int i = 0; i < 5; i++)
    {
        /* 먼저 우리가 알고 있는 5가지 도형 중 하나 인지 판단. */
        bool Flag = true;
        for (int j = 0; j < 4; j++)
        {
            /* 계산해 놓은 4개의 좌표가, 5가지 도형 중 하나를 이루는지 판단. */
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            if ((nx < 0 || ny < 0 || nx >= N || ny >= N) || board[nx][ny] != Value)
            {
                Flag = false;
                break;
            }
        }
        if (Flag == true)
        {
            /* 만약, 우리가 판단했던 지울 수 있는 도형이라면 ? */
            /* 이번에는, 검은색 블록 2개를 떨어뜨려서 꽉 채운 도형으로 만들 수 있는지 판단. */
            bool Flag2 = true;
            for (int j = 4; j < 6; j++)
            {
                int nx = x + dx[i][j];
                int ny = y + dy[i][j];
                if ((nx < 0 || ny < 0 || nx >= N || ny >= N) || board[nx][ny] != 0)
                {
                    Flag2 = false;
                    break;
                }
 
                /* 검은색 블록을 채울 수 있다면 */
                /* 해당 검은색 블록을 그 칸 까지 떨어뜨릴 수 있는지 판단. */
                for (int k = nx; k >= 0; k--)
                {
                    if (board[k][ny] != 0)
                    {
                        Flag2 = false;
                        break;
                    }
                }
                if (Flag2 == false) break;
            }
            if (Flag2 == true) return i;
        }
    }
    return -1;
}
 
void Remove(int x, int y, int Idx, vector<vector<int>> &board)
{
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[Idx][i];
        int ny = y + dy[Idx][i];
        board[nx][ny] = 0;
    }
}
 
int solution(vector<vector<int>> board) 
{
    Setting();
    N = board.size();
    int answer = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == 0)continue;
 
            int Result = Check(i, j, board);
            if (Result != -1)
            {
                Remove(i, j, Result, board);
                answer++;
                j = -1;
            }
        }
    }
 
    return answer;
}