[백준] Puyo Puyo

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

11559번: Puyo Puyo

구현, 시뮬레이션 문제입니다.

 

문제부터 간단하게 요약하면, 

애니팡 같이 뿌요뿌요라는 게임이 있습니다. 이 게임에서는 뿌요들이 4개이상 모이면 폭발하는데 매번 터질수 있는 푸요들이 모두 터진후 뿌요들이 내려옵니다.

 

그리고 또 다시 터질 것이 있다면 상태가 변화하지 않을 때 까지 반복됩니다. 이 반복이 총 몇번 일어나는지를 계산해 주는 것을 구현해야 합니다.

 

<Solution>

- 푸요의 폭발

각 푸요에 대해 bfs를 통해 탐색을 해서 만약 4개 이상이라면 폭발하고, 아니라면 폭발이 복구되는 형태로 구현하였습니다. 제 코드 상에서는 복구를 해주어야 하므로 좌표를 기록할 수 있도록 하였습니다.

 

- 아래에서 폭발이 있어서 푸요가 떨어지는 로직

만약 위의 푸요 밑에서 폭발이 일어나 한 화면의 폭발이 모두 끝난 후 내려와야 하는 경우들이 생깁니다. 이 때, 가장 아래에서 두번째 줄에 위치한 푸요부터 아래를 살펴보고 만약 ' . ' 이면 swap을 시키는 형태로 구현하였습니다.

 

실제 전체 구현은 아래와 같습니다. 

#include <iostream>
 
using namespace std;
#define MAXH (12)
#define MAXW (6)
char map[MAXH+2][MAXW+2];
 
int d_row[] = {0, 0, 1, -1};
int d_col[] = {1, -1, 0, 0};
 
void InputData(){
    for (int i=1; i<=MAXH; i++){
        cin >> &map[i][1];
    }
}
 
int cnt; // 연결된 거 갯수
int visited[MAXH+2][MAXW+2];
int memorize_array[2][12*6+10];
 
void ff(int r, int c, char alphabet){
 
    if(map[r][c] != alphabet || visited[r][c] == 1) return;
    map[r][c] = '.';
    visited[r][c] = 1;
    memorize_array[0][cnt] = r; memorize_array[1][cnt] = c;
    cnt++;
 
    for(int i = 0; i<4; i++){
        int new_r = r+d_row[i];
        int new_c = c+d_col[i];
 
        if(!(1<= new_r && new_r<=MAXH && 1<= new_c && new_c <= MAXW)) continue;
         
        ff(new_r,new_c, alphabet);
 
    }
 
}
 
void solution(int& ans){
    int boom_flag = 1;
    while(boom_flag){
 
 
        boom_flag = 0;
        //visited 초기화
        for(int i =0; i<MAXH+2; i++){
            for(int j = 0; j<MAXW+2 ; j++){
                visited[i][j] = 0;
            }
        }
 
        for(int r=1; r<=12; r++){
            for(int c =1; c<=6; c++){
                if('A'<=map[r][c] && map[r][c] <='Z'){
                    cnt = 0; 
                    char p = map[r][c];
                    ff(r,c, map[r][c]);
                    // 4개보다 작으면 원상복구
                    if(cnt < 4){
                        for(int i = 0; i<cnt; i++){
                            map[memorize_array[0][i]][memorize_array[1][i]] = p;
                        }
                    }
                    boom_flag |= (cnt >=4) ? 1 : 0;
                }
            }
        }
         
        // boomflag가 1이면 성공 && map에서 터진 부분들이 내려와야함
        if(boom_flag){
            ans++;
            for(int r =11; r>=1; r--){
                for(int c=1; c<=6; c++){
                    if('A'<=map[r][c] && map[r][c] <='Z'){
                        // 내릴 수 있다면 내려야함
                        for(int k = r+1; k<=12; k++){
                            if(map[k][c] == '.'){
                                // swap
                                map[k][c] = map[k-1][c];
                                map[k-1][c] = '.';
                            }
                            else{
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
}
 
int main(){
    int t, ans = -1;
    InputData();

    ans = 0;

    solution(ans);
    
    cout << ans << endl;

    return 0;
}