[백준][11559번] Puyo Puyo [cpp, c++]

백준 11559번 Puyo Puyo

• 전형적인 시뮬레이션 문제이다.
• https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

• 풀이방법
  1) R, G, B, P, Y 순으로 BFS를 통해 4개가 뭉쳐있는 곳을 찾아 check2배열에 표시해놓는다.
  2) 터트린 부분을 위에서 부터 밑으로 한칸 씩 채운다.

• 함수 설명

  • bfs() : bfs 탐색
  • move_block(int x, int y): y열에서 x칸까지 1칸씩 이동
  • delete_block(): 몇 번 이동할지 결정

• ※주의사항: BFS할 때 위에서 한번만 훝는 씩이 아닌 각각 색깔에 대한 검사가 필요하다.
• ex) R를 검사할 때 R를 한번만 검사하게 되면, 맨 밑에 있는 (2*2) R을 검사하지 못한다.
  ......
  ......
  ......
  ......
  ......
  ......
  ......
  YY....
  RR....
  BBYY..
  RRGB..
  RRGB..
  이런 경우를 대비해서....

#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
char puyo[13][7]; //12 * 6의 puyo 공간
bool check1[13][7];
int check2[13][7];
char color[6] = { 'R', 'G', 'B', 'P', 'Y' };
int nx[5] = { 1,0,-1,0 };
int ny[5] = { 0,1,0,-1 };
int flag;
int ans;
// R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다
queue<pair<int, int>> q;
queue<pair<int, int>> q2;



void bfs(char color) { //어느 것을 터뜨릴지 찾는 bfs()

    int cnt = 1;//puyo의 크기
    //큐에 값을 넣어줌
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int dx = x + nx[i];
            int dy = y + ny[i];
            if (dx >= 12 or dx < 0 or dy >= 6 or dy < 0) continue;
            if (check1[dx][dy] == true) continue;
            if (puyo[dx][dy] == '.') continue;
            if (puyo[dx][dy] == color) {
                q.push(make_pair(dx, dy));
                q2.push(make_pair(dx, dy));
                check1[dx][dy] = true;
                cnt++;
            }
        }
    }
    if (cnt < 4) while (!q2.empty()) q2.pop();
    if (cnt >= 4) { 
        while (!q2.empty()) {
            flag = 1;
            int x1 = q2.front().first;
            int y1 = q2.front().second;
            q2.pop();
            check2[x1][y1] = 1;
        }
    }
}




void move_block(int x, int y) { //1칸씩 이동

    for (int i = x; i > 0; i--) {
        puyo[i][y] = puyo[i - 1][y];
    }
    puyo[0][y] = '.';
}


void delete_block() {  

    for (int i = 0; i < 6; i++) {
        int cnt = 0;
        for (int j = 0; j < 12; j++) {
            if(check2[j][i]==1) move_block(j, i);
        }

    }

}



void test_sol() {
    while (1) {
        flag = 0;

        for (int i1 = 0; i1 < 5; i1++) {
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (check1[i][j] == false && puyo[i][j] == color[i1]) {
                        check1[i][j] = true;
                        q.push(make_pair(i, j));
                        q2.push(make_pair(i, j));
                        bfs(color[i1]);

                    }
                }
            }
        }
        delete_block();
        if (flag == 1) ans++;
        if (flag == 0) break;
        memset(check2, 0, sizeof(check2));
        memset(check1, 0, sizeof(check1));
    }
    cout << ans;
}




int main(void) {
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> puyo[i][j];
        }
    }
    test_sol();

}