프로그래머스 - [1차] 프렌즈4블록 (Lv.2)

문제 링크

• 프렌즈4블록

문제 설명

• 길이가 m x n 인 격자판이 주어지고 그 위에 A~Z 중 하나의 문자가 적혀있다.
• 2 x 2 칸에 같은 문자가 있을 경우 사라지면서 점수를 얻는다.
  • 중복된 칸을 허용한다.
• 삭제될 수 있는 칸들은 동시에 삭제된다.
• 삭제되고 빈칸이 생긴 경우 위쪽에 있는 칸들이 아래로 내려와서 채워진다.

문제 접근

• m을 행, n을 열로 문제에서 주어졌는데, 본인은 늘 N을 행으로 M을 열로 생각하며 문제를 풀기 때문에 헷갈리지 않도록 미리 조치를 취해두었다.
• (0,0)부터 차례대로 탐색하며 2x2 격자 안에 모두 같은 문자가 적혀 있는지 확인한다. 만약 4개의 문자가 모두 같다면 탐색이 끝난 후 다른 블록들과 함께 동시에 지울 수 있도록 removed 배열에 1로 표시해둔다.
• removed 배열에 1로 표현된 칸들은 모두 사라진다. 이때 격자판에는 * 로 표현하도록 한다. 칸이 사라질 때마다 사라진 칸의 개수를 센다.
  • 사라진 칸이 없는 경우 탐색을 종료한다.
• 사라진 칸을 채운다.

구현(All Pass)

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

int movement[3][2] = {
    {0,1}, {1,0}, {1,1}
};
vector<string> cboard;
int N, M, ans;

bool checkFourBlock(int x, int y){
    char ch = cboard[x][y];
    for(int i=0; i<3; i++){
        int nextX = x + movement[i][0];
        int nextY = y + movement[i][1];
        
        if(nextX<0 || nextX>=N || nextY<0 || nextY>=M) 
            return false;
        if(cboard[nextX][nextY] != ch)
            return false;
    }
    return true;
}

bool setRemoveBlock(){
   vector<vector<bool>> removed(30, vector<bool>(30, false));
    
    for(int r=0; r<N; r++){
        for(int c=0; c<M; c++){
            if(cboard[r][c]=='*') continue;
            if(checkFourBlock(r,c)){
                removed[r][c] = true;
                for(int i=0; i<3; i++){
                    int nextX = r + movement[i][0];
                    int nextY = c + movement[i][1];
                    removed[nextX][nextY] = true;
                }
            }
        }
    }
    
    // remove blocks
    int flag = 0;
    for(int r=0; r<N; r++){
        for(int c=0; c<M; c++){
            if(removed[r][c]){
                cboard[r][c] = '*';
                ans++;
                flag=1;
            }
        }
    }
    if(flag==0) return false;
    return true;
}

void moveDownBlocks(){
    string str = string(M, '*');
    vector<string> nboard(N, str);
    
    for(int c=0; c<M; c++){
        int curR = N-1;
        for(int r=N-1; r>=0; r--){
            if(cboard[r][c]=='*') continue;
            nboard[curR--][c] = cboard[r][c];
        }
    }
    
    cboard = nboard;
}

int solution(int m, int n, vector<string> board) {
    cboard = board;
    N = m, M = n;
    
    while(true){
        if(setRemoveBlock()==false)
            break;
        moveDownBlocks();
    }
    
    return ans;
}