📒활용개념

하드코딩의 끝을 볼 수 있었던 문제였다.

📌문제설명

같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다. 만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
예시)
m n. board answer
4 5 ["CCBDE", "AAADE", "AAABF", "CCBBF"] 14

예제의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.

📌구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;
vector<vector<int> > map;
vector<string> boards;
int low[3]={1,0,1};
int col[3]={0,1,1};

void check(vector<string> board){
    for(int i=0; i<board.size()-1; i++){
        for(int j=0; j<board[i].size()-1; j++){
            bool ch =true;
            for(int k=0; k<3; k++){
                if(board[i][j]!=board[i+low[k]][j+col[k]]){
                    ch=false;
                    break;
                }
            }
            if(board[i][j]!='*'){
                if(ch){
                    map[i][j]=1;
                    for(int k=0; k<3; k++){
                        map[i+low[k]][j+col[k]]=1;
                    }
                }
            }
        }
    }
}

int clear (){
    int cnt=0;
    
    for(int i=0; i<boards[0].size(); i++){
        bool ch=false;
        for(int j=0; j<boards.size(); j++){
            if(map[j][i]==1){
                cnt++;
                boards[j][i]='*';
                ch=true;
                map[j][i]=0;
            }
        }
        if(ch){
            for(int j=boards.size()-2; j>=0; j--){
                if(boards[j][i]!='*'&&boards[j+1][i]=='*'){
                    int tmp=j;
                    while(tmp<boards.size()-1&&boards[tmp+1][i]=='*'){
                        boards[tmp+1][i]=boards[tmp][i];
                        boards[tmp][i]='*';
                        tmp++;
                    }
                }
            }
        }
    }
    
    return cnt;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    int cnt;
    
    boards=board;
    
    for(int i=0; i<m; i++){
        vector<int> t;
        for(int j=0; j<n; j++){
            t.push_back(0);
        }
        map.push_back(t);
    }

    check(boards);

    cnt=clear();
    while(cnt!=0){
        answer+=cnt;
        check(boards);
        cnt=clear();
    }
    
    return answer;
}

📌주의점

경우의 수가 너무 많은 문제다. 그 때문에 모든 경우의 수를 고려한 코딩을 해야한다.