(C++) - 백준(BOJ) 11559번 : Puyo Puyo

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

구현문제였습니다.

 

풀이방법

 1. 모든좌표를 돌면서 터뜨려봅니다. bfs를 통해 같은 영역이 있으면 없애줄 좌표들의 후보 queue인 popQ에 저장합니다. 같은 영역이 4이상이라면 popQ를 하나씩 빼주면서 해당 좌표의 값을 '.'로 바꿔줍니다.

 

 2. 터진 후에는 내립니다. 세로로 한 열씩 떼서 확인합니다. 필드의 행,열의 값이 '.'이 아니라면 queue에 넣어줍니다. 최하단부터 queue에서 하나씩 빼서 필드에 채우며 정리해줍니다.

 

 3. 터뜨릴게 남아있다면 ans++ 후 1-2구간을 반복합니다. 없으면 반복구간을 탈출한 후 답을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
char board[12][6];
int ck[12][6];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int ans;
int boomed(int i, int j, char c){
    queue <pii> q;
    queue <pii> popQ;
    q.push({i,j});
    popQ.push({i,j});
    ck[i][j] = 1;
    int area = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0 ; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= 12 || 0 > ny || ny >= 6) continue;
            if(ck[nx][ny] || board[nx][ny]!=c) continue;
            ck[nx][ny] = 1;
            q.push({nx,ny});
            popQ.push({nx,ny});
            area++;
        }
    }
    if(area>=4){
        while(!popQ.empty()){
            int x = popQ.front().first;
            int y = popQ.front().second;
            board[x][y] = '.';
            popQ.pop();
        }
    }
    return area;
}

void goDown(){
    queue <char> q;
    for(int j = 0; j < 6; j++){
        for(int i = 11; i >= 0; i--)
            if(board[i][j]!='.') 
                q.push(board[i][j]);
        for(int i = 11; i >= 0; i--) board[i][j] = '.';
        
        int piv = 11;
        while(!q.empty()){
            int c = q.front();
            q.pop();
            board[piv--][j] = c;
        }
    }
}

int main(){
    for(int i = 0; i < 12; i++) cin >> board[i];
    while(1){
        int area = 0;
        memset(ck,0,sizeof(ck));

        for(int i = 0; i < 12; i++)
            for(int j = 0; j < 6; j++)
                if(board[i][j]!='.')
                    area = max(area,boomed(i,j,board[i][j]));

        goDown();

        if(area < 4) break;
        else ans++;
    }
    cout << ans;
}