[프로그래머스/C++] 블록 게임 (2019 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 3가지 모양의 블럭을 90도로 회전한 모양이 존재할 수 있으며, 위에서 1*1 크기의 사각형을 떨어뜨려 사각형 모양으로 채울 수 있으면, 블럭이 삭제되는 문제다.

 

즉, 블럭이 삭제되기 위해서는 1*1 크기의 블럭이 위에서만 떨어지기 때문에 삭제가 가능한 블럭을 쉽게 구분이 가능하다는 뜻이다.

 

예를 들면 L 모양 또는 ㅗ 모양의 블럭은 위에서 블럭을 떨어뜨려 사각형을 만들 수 있지만, ㄱ 모양 ㅜ 모양의 블럭은 위에서 블럭을 떨어뜨려도 사각형으로 만들지 못한다.

 

그러므로 아래 5가지 경우의 블럭만 제거가 가능하다.

 

이제 제거가 가능한 블럭들을 알았으므로, 제거가 가능한 조건에 대해 생각해보자

 

블럭을 제거하기 위해서는 위에서 블럭을 떨어뜨리기 때문에 블럭이 채워져야 하는 부분의 위쪽에 다른 블럭들이 없어야 한다.

즉, 화살표가 표시된 부분의 위쪽에 다른 블럭이 막고 있는지 검사를 해주면 해결할 수 있는 문제다.

 

이후 조건에 따라 코드를 구현했는데, 예외 케이스가 있었다.

 

구현 방법을 럭의 개수가 적었기 때문에 블럭의 가장 좌상단에 있는 블럭을 기준으로 모양을 탐색을 시켰고, 

단순히 2중 for문을 이용해 x축의 블럭을 탐색하고 y를 1증가시켜 순차적으로 탐색하도록 코드를 구현했다.

 

그래서 아래와 같은 경우가 나올 시, 제거가 되어야 하는 블럭이 제거가 되지 않는 경우가 생겼다.

그래서 이 문제를 해결하기 위해 y축을 기준으로 내려갈 때마다 x축으로 증가하는 방향에서 탐색하고 x축에서 감소하는 방향으로 두번 탐색시켜 예외 케이스를 해결했다...

  

 

[아이디어 정리]

1. 블럭의 모양을 파악해 제거가 가능한 블럭인지 찾는다.
2. 제거가 가능한 블럭일 경우 위에 다른 블럭이 막고 있는지 검사한다.
3. 이후 제거가 가능하면 제거하고, 다음 블럭을 탐색한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool search(int y, int x, vector<vector<int>> &board) // x줄의 y까지 탐색
{
    for (int i=0; i<y; i++)
    {
        if (board[i][x]!=0)
            return false;
    }
    return true;    
}

bool removeFunc(int y, int x, vector<vector<int>> &board)
{// 지울 수 있는 모양이 5개 뿐이다. y는 아래가 +
    int ny, nx, bs=board.size();
    ny=y,nx=x;
    int num=board[y][x];
    bool flag=false;
    if (y+1<bs&&x+2<bs)//ㄴ
    {
        if (search(y+1,x+1,board)&&search(y+1,x+2,board))
        {
            if (num==board[y+1][x]&&num==board[y+1][x+1]&&num==board[y+1][x+2])
            {
                board[y][x]=0,board[y+1][x]=0,board[y+1][x+1]=0,board[y+1][x+2]=0;
                flag=true;
            }
        }
    }
    
    if (!flag&&y+2<bs&&x-1>=0) //좌우반전L
    {
        if (search(y+2,x-1,board))
        {
            if (num==board[y+1][x]&&num==board[y+2][x]&&num==board[y+2][x-1])
            {
                board[y][x]=0,board[y+1][x]=0,board[y+2][x]=0,board[y+2][x-1]=0;
                flag=true;
            }
        }        
    }
    if (!flag&&y+2<bs&&x+1<bs) //L
    {
        if (search(y+2,x+1,board))
        {
            if (num==board[y+1][x]&&num==board[y+2][x]&&num==board[y+2][x+1])
            {
                board[y][x]=0,board[y+1][x]=0,board[y+2][x]=0,board[y+2][x+1]=0;
                flag=true;
            }
        }
    }
    if (!flag&&y+1<bs&&x-2>=0) //ㄴ반전
    {
        if (search(y+1,x-1,board)&&search(y+1,x-2,board))
        {
            if (num==board[y+1][x]&&num==board[y+1][x-1]&&num==board[y+1][x-2])
            {
                board[y][x]=0,board[y+1][x]=0,board[y+1][x-1]=0,board[y+1][x-2]=0;
                flag=true;
            }
        }
    }
    if (!flag&&y+1<bs&&x-1>=0&&x+1<bs)
    {
        if (search(y+1,x+1,board)&&search(y+1,x-1,board))
        {
            if (num==board[y+1][x]&&num==board[y+1][x-1]&&num==board[y+1][x+1])
            {
                board[y][x]=0,board[y+1][x-1]=0,board[y+1][x]=0,board[y+1][x+1]=0;
                flag=true;
            }
        }
    }
    if (!flag)
    {
        return false;
    }
    else
    {
        return true;
    }
    
}
int solution(vector<vector<int>> board) {
    int answer = 0;
    for (int i=0; i<board.size(); i++)
    {
        for (int j=0; j<board.size(); j++)
        {
            if (board[i][j]!=0)
            {
                if (removeFunc(i,j,board))
                {
                    answer+=1;
                }
            }
            if (board[i][board.size()-j-1]!=0)
            {
                if (removeFunc(i,board.size()-j-1,board))
                {
                    answer+=1;
                }
            } 
        }
    }
    
    return answer;
}

 

---

문제를 보고 특별한 예외가 없을 거라고 생각해서 바로 구현했는데, 생각하지 못한 예외가 있었다

다른 방법으로 구현하는게 나았으려나...?

프로그래머스