(C++) 백준 11559 Puyo Puyo

문제 및 풀이

https://www.acmicpc.net/problem/11559

이런 유형 은근 많이나오는거같다;;

이문제에서 주의해야 할 점은 뿌요가 터지고 바로 맵을 바로 갱신하는게 아니라 맵을 한바퀴 모두 돈 다음에 맵을 갱신해야 한다는 것이다.
또 한번 맵을 돌 때 뿌요가 두번 터져도 답은 한번으로 카운트 해야한다. (콤보가 터진 횟수를 구하는게 답이다.)

구현 자체는 평이했다

• 먼저 dfs로 현재 뿌요와 같은 뿌요가 4개 이상인지 판단하고, 4개 이상이면 터진걸로 생각해서 맵을 빈 공간(.)으로 변경
• 변경된 맵에 대해 갱신할때 큐를 사용해서 문자만 넣고 빼는식으로 구현했는데.. 맵이 커지면 오버헤드가 커질거같다. 다음처럼 조건을 통해 맵을 갱신하는 방법을 사용하자.

for (int j = 0; j < 6; j++)
	while(1){
    	bool fall=0;
        for (int i = 11; i >=1 ; i--)
        if(map[i][j]=='.'&&map[i-1][j]!='.'){
        	map[i][j]=map[i-1][j];
        	map[i-1][j]='.';
        	fall=1; 
            }
        if(!fall)
        break;
   }

전체코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


string str;
char map[15][7];
bool isvisited[15][7];
int ans;

const int height = 12;
const int width = 6;
const pair<int, int> dir[4] = {{0,1},
                               {0,-1},
                               {1,0},
                               {-1,0}};


void downTheMap(){
    queue<char> tmp_q;

    for(int i=0; i<width; i++){
        for(int j=height-1; j>=0; j--){
            if(map[j][i]!='.') tmp_q.push(map[j][i]);
        }
        for(int j=height-1; j>=0; j--){
            if(!tmp_q.empty()) {
                map[j][i]=tmp_q.front();
                tmp_q.pop();
            }
            else map[j][i]='.';
        }
    }
}



bool dfs(int y, int x){
    for(int i=0; i<height; i++) 
    	for(int j=0; j<width; j++) 
        	isvisited[i][j]=false;
            
    queue<pair<int, int>> q;
    queue<pair<int, int>> cache;
    int cnt=0;
    q.push({y,x});
    cache.push({y,x});

    while(!q.empty()){

        int ny = q.front().first;
        int nx = q.front().second;
        q.pop();

        if(isvisited[ny][nx]) continue;
        isvisited[ny][nx] = true;
        cnt++;

        for(int i=0; i<4; i++){
            int yy = ny + dir[i].first;
            int xx = nx + dir[i].second;

            if(yy<0 || xx<0 || yy>=height || xx>=width) continue;
            if(map[y][x]!=map[yy][xx]) continue;
            q.push({yy,xx});
            cache.push({yy,xx});
        }
    }


    if(cnt>=4) {
        while(!cache.empty()){
            int ty = cache.front().first;
            int tx = cache.front().second;
            cache.pop();
            map[ty][tx]='.';
        }
        return true;
    }
    return false;
}



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=0; i<height; i++){
        cin>>str;
        for(int j=0; j<width; j++){
            map[i][j] = str[j];
        }
    }


    while(1){
        bool pop= false;

        for(int i=0; i<width; i++){
            for(int j=height-1; j>=0; j--){
                if(map[j][i]!='.') {
                    if(dfs(j, i)) {
                        pop=true;
                    }
                }
            }
        }

        if(!pop) break;
        downTheMap();
        ans++;
    }

    cout<<ans;

}