백준 11559번: Puyo Puyo

백준 11559번: Puyo Puyo

11559번: Puyo Puyo

뿌요뿌요 게임, 이미지 출처 : https://bab2min.tistory.com/206

 

뿌요뿌요를 어렸을 때 했던 기억은 있지만 그 때는 재밌는 게임인줄 몰랐다. 고등학생때였나? 뿌요뿌요랑 조금은 다르지만 비슷한 게임인 애니팡을 즐겨했던 것 같다. 그것도 한달도 안하고 접긴했지만

 

문제에 대한 이해는 뿌요뿌요 게임을 원래 알고있어서 블록이 터지고 움직이는 과정이 어떤지는 이해가 되었다. 여기서 구하는 것이 어떤 것인지만 확인하고 시뮬레이션 코드를 작성하면 된다. 시뮬레이션 코드에 딱히 정답은 없고 남이 작성한 시뮬레이션 코드를 보기란 쉬운것이 아닌 것 같다. 시뮬레이션은 그냥 작동 순서를 이해하고 직접 부딪히는것이 답이다! 제출할 때 한 번 시간초과가 났었는데 블록이 터지고 위쪽 블록이 내려오는 과정에서 빈칸을 바로바로 채우는게 아닌 한칸한칸 내려와 채우게하니까 반복문을 여러번 돌려서 시간이 오버되었던 것 같다. 블록 사이에 빈공간이 생기면 바로 채우는 방식으로 바꾸어서 해결했다.

 

#include<iostream>
#include<cstring>
#include<queue>
#define W 6
#define H 12
using namespace std;
struct p{
    int h;
    int w;
};
queue<p> q;
queue<p> slash;
char field[H][W];
bool visited[H][W];
int boom=0; //연쇄
//터지는 뿌요들을 변환하는 함수
bool puyo(){
    bool flag = false;
    int dirW[] = {1,-1,0,0};
    int dirH[] = {0,0,1,-1};
    int h, w, dh, dw, cnt = 1;  //4개인지 확인
    while(!q.empty()){
        h = q.front().h;
        w = q.front().w;
        q.pop();
        slash.push({h, w});
        for(int i = 0; i < 4; i++){
            dh = h + dirH[i];
            dw = w + dirW[i];
            if(dh < 0 || dh >= H || dw < 0 || dw >= W) continue;
            if(visited[dh][dw]) continue;
            if(field[h][w] != field[dh][dw]) continue;
            visited[dh][dw] = true;
            q.push({dh, dw});
            cnt += 1;
        }
    }
    if(cnt >= 4){
        while(!slash.empty()){
            h = slash.front().h;
            w = slash.front().w;
            slash.pop();
            field[h][w] = '.';
        }
        flag = true;
        cnt = 1;
    }
    else{
        while(!slash.empty()){
            slash.pop();
        }
    }
    return flag;
}
void movePuyo()
{
    for (int j = 0; j < W; j++)
    {
        int dist = H - 1;
        for (int i = H - 1; i >= 0; i--)
        {
            if (field[i][j] != '.')
            {
                if(dist == i){
                    dist -= 1;
                    continue;
                }
                else{
                    field[dist][j] = field[i][j];
                    field[i][j] = '.';
                    dist -= 1;
                }
            }
            
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> field[i][j];
        }
    }
   
    while(true){
        memset(visited, false, sizeof(visited));
        bool flag = false;
        for(int i = H-1; i >= 0; i--){
            for(int j = 0; j < W; j++){
                if(field[i][j] == '.') continue;
                q.push({i, j});
                visited[i][j] = true;
                if(puyo())
                    flag = true;
            }
        }
        if(flag == false) break;
        movePuyo(); 
        boom+=1;
    }
    cout << boom;
    return 0;
}