[백준 11559번] Puyo Puyo

문제 링크: https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

<문제 풀이> BFS, 시뮬레이션

1. BFS로 한 뿌요와 4방향으로 연결된 동일한 뿌요의 개수를 센다 

2. 만약 동일한 뿌요의 개수가 4개 이상이면 해당 뿌요를 터트린다.

3. 모든 뿌요를 떨어뜨린다.

 

만약 터트릴 뿌요가 없으면 종료

 

 

 

<C++ 소스 코드>

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
 
#define X first
#define Y second
 
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
 
const int r = 12;
const int c = 6;
 
char board[r][c];
bool visited[r][c];
 
void boom(int x, int y) {
    queue<pair<int, int > > Q;
    Q.push({ x, y });
    char target = board[x][y];
    board[x][y] = '.';
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c)continue;
            if (board[nx][ny] != target) continue;
            board[nx][ny] = '.';
            Q.push({ nx, ny });
        }
    }
}
 
void fall() {
    for (int y = 0; y < c; y++) {
        char moved[r];
        int idx = 0;
        for (int x = r - 1; x >= 0; x--) {
            if (board[x][y] != '.') {
                moved[idx++] = board[x][y];
            }
        }
        for (int i = 0; i < idx; i++) {
            board[r - 1 - i][y] = moved[i];
        }
        for (int i = idx; i < r; i++) {
            board[r - 1 - i][y] = '.';
        }
    }
}
 
bool bfs() {
    bool ret = false;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j] != '.' && !visited[i][j]) {
                queue<pair<int, int> > Q;
                Q.push({ i, j });
                visited[i][j] = true;
                int cnt = 1;
                while (!Q.empty()) {
                    auto cur = Q.front(); Q.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= r || ny >= c)continue;
                        if (visited[nx][ny] || board[nx][ny] != board[cur.X][cur.Y])continue;                    
                        visited[nx][ny] = true;
                        cnt++;
                        Q.push({ nx, ny });
                    }
                }
                if (cnt >= 4) { // 뿌요들이 4개 이상 모이면
                    ret = true;
                    boom(i, j);
                }
            }
        }
    }
    fill(&visited[0][0], &visited[r - 1][c], 0);
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
    int res = 0;
    while (bfs()) {
        res++;
        fall();
    }
    cout << res;
    return 0;
}