[KAKAO_2018] 프렌즈 4블록

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

2x2 크기의 동일 블록에 대한 블록게임을 구현하는 문제였다.

먼저 루프를 돌며 같은 모양을 갖는 블록들모임이 존재하는지 확인하고, 해당되는 갯수를 구해 정답에 더해주면 된다.

 

만약 그 갯수가 0이라면 지울 블록이 없다는 의미이므로 더이상 진행하지 않고 빠져나와 정답을 출력하면 된다.

 

핵심은 70번째 줄로 블록을 내려준 뒤에 다음 행 (바로 위 행) 부터 조사해주는 것이다. 저 break;를 안하면 통과하지 않는 테스트케이스 4건이 생긴다. 왜냐하면 기껏 갱신해놓은 r에 루프를 더 돌아 ' '가 아닌 것이 나오면 덮어써버리기 때문이다.

#include <string>
#include <vector>
using namespace std;
 
vector<vector<bool> > check;
int height, width;
typedef struct dir{
    int dr, dc;
}dir;
dir d[4] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
void falsing(){
    for(int r=0; r<height; r++){
        for(int c=0; c<width; c++){
            check[r][c] = false;
        }
    }
}
int solution(int R, int C, vector<string> board) {
    int answer = 0;
    height = R;
    width = C;
    check.assign(R, vector<bool>(C, false));
    while(1){
        int curErase = 0;
        // 1. erase
        for(int r=0; r<R-1; r++){
            for(int c=0; c<C-1; c++){
                char curCharacter = board[r][c];
                if(curCharacter == ' ') continue;
                bool allSame = true;
                for(int i=0; i<4; i++){
                    int nr = r + d[i].dr;
                    int nc = c + d[i].dc;
                    if(board[nr][nc] != curCharacter){
                        allSame = false;
                        break;
                    }
                }
                if(allSame){ // 4개 다 같으면
                    for(int i=0; i<4; i++){
                        int nr = r + d[i].dr;
                        int nc = c + d[i].dc;
                        if(!check[nr][nc]){
                            check[nr][nc] = true;
                            curErase++;
                        }
                    }
                }
            }
        }
        answer += curErase;
        if(curErase == 0) break; // 안지워진다면 끝. // 지워주기.
        
        for(int r=0; r<R; r++){
            for(int c=0; c<C; c++){
                if(check[r][c]){
                    board[r][c] = ' ';
                }
            }
        } 
        
        // 2. go down
        for(int c=0; c<C; c++){
            for(int r=R-1; r>=0; r--){
                if(board[r][c] == ' '){
                    for(int n_r = r-1; n_r >= 0 ; n_r--){
                        if(board[n_r][c] != ' '){
                            board[r][c] = board[n_r][c];
                            board[n_r][c] = ' ';
                            break;
                        }
                    }
                }
            }
        }        
        falsing();
    }
    return answer;
}