[C++] 백준 BOJ 11559 Puyo Puyo

문제링크 : https://boj.kr/11559

1. 블럭은 4개 이상 모였을 때 터짐

2. 동시에 터지는 것은 하나의 연쇄 단계임

3. 한 연쇄 단계에 블럭이 터진 이후 중력에 의해 블럭이 아래로 내려감

// BOJ 11559 Puyo Puyo
#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
char arr[14][8];
bool visited[14][8];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
 
struct pt {
    int x, y;
};
int p = 0; // 현재 탐색 위치
 
bool puyo(pt input) {
    int ix = input.x;
    int iy = input.y;
    char ans = arr[ix][iy]; // 탐색할 문자
    if(ans == '.')
        return false;
    queue<pt> Q; // BFS를 위한 큐
    queue<pt> memory; // 탐색한 노드 저장
    Q.push(input);
    memory.push(input);
    visited[ix][iy] = true;
    int cnt = 0;
    while (!Q.empty()) {
        pt cur = Q.front();
        Q.pop();
        int x = cur.x;
        int y = cur.y;
        memory.push({x, y});
        cnt++;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (arr[a][b] == ans && !visited[a][b]) {
                visited[a][b] = true;
                memory.push({a, b});
                Q.push({a, b});
            }
        }
    }
 
    // 4개 이상 같은 색 발견시 뿌요 가능
    if (cnt >= 4) {
        while (!memory.empty()) {
            pt del = memory.front();
            memory.pop();
            arr[del.x][del.y] = '.';
        }
        return true;
    } else
        return false;
}
 
// 중력에 의해 블럭 아래로
void bDown() {
    int M = 0; // 열 좌표
    while (++M <= 6) {
        if(arr[12][M] == 'X')
            continue;
        int N = 12; // 행 좌표
        bool flag = false;
        for (int i = 12; i >= 1; i--) {
            // 빈 공간이 아니라면
            if (arr[i][M] != '.') {
                flag = true;
                // 블럭 아래로 내림
                char tmp = arr[i][M];
                arr[i][M] = '.';
                arr[N--][M] = tmp;
            }
        }
        // 블럭을 찾지 못하였다면 X로 표시하여
        // 다음 탐색때부턴 스킵
        if (!flag)
            arr[12][M] = 'X';
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    memset(arr, 'X', sizeof(arr));
 
    for (int i = 1; i <= 12; i++)
        cin >> arr[i] + 1;
 
    int result = 0;
    bool isPuyo = false;
    while (true) {
        if(++p > 6 && isPuyo){
            result++;
            // 다음 뿌요를 위하여 visited 초기화
            memset(visited, false, sizeof(visited));
            // 블럭 아래로 떨어뜨리고
            // 다시 처음부터 진행
            bDown();
            isPuyo = false;
            p = 0;
            continue;
        }
        else if(p > 6 && !isPuyo)
            break;
        // 현재 열에 블럭이 없다면 continue
        if (arr[12][p] == 'X' || arr[12][p] == '.')
            continue;
        for(int i = 12; i >= 1; i--) {
            if (puyo({i, p})) {
                isPuyo = true;
            }
        }
    }
    cout << result;
 
    return 0;
}