11559. Puyo Puyo

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

11559번: Puyo Puyo

 

풀이

먼저 문제의 조건을 보고, 다음 사항에 주의한다.

1. 뿌요는 같은 색깔이 4개 이상 상하좌우로 모여 있어야 터진다. 두세 개만 모여 있어도 터지는 것으로 착각하지 않도록 한다.
2. 터질 수 있는 뿌요가 여러 그룹이 있으면 동시에 터져야 하며, 1연쇄로 취급한다. 즉, 만족하는 그룹이 3개가 있든 10개가 있든 1연쇄로 취급하며, 뿌요를 아래로 떨어뜨리는 처리는 그룹을 동시에 전부 터뜨린 뒤 해야 한다.

주어진 필드에서 연쇄가 몇 연속으로 이어지는지 찾는 로직은 다음과 같다.

1. 주어진 필드에서 같은 색깔이 4개 이상 모인 뿌요를 찾아서 모두 터뜨린다. 폭발 가능한 뿌요는 BFS를 활용하여 찾을 수 있다. 터뜨린 칸은 빈칸(.)으로 채운다.
2. 1에서 최소 한 그룹의 폭발이라도 일어났다면 연쇄 횟수를 1 증가시킨다.
3. 뿌요들을 아래로 떨군다. 이는 각 세로열의 뿌요를 아래쪽부터 재배열하는 방식으로 구현할 수 있다.
4. 연쇄가 더 이상 일어나지 않을 때까지 1~3을 반복한다. 2에서 연쇄 횟수가 증가하지 않았다면 연쇄가 더 이상 일어나지 않는다는 뜻이므로 반복을 종료하면 된다.

 

소스코드

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
using Pair = pair<int, int>;

char field[12][6];
bool checked[12][6];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int ans;

// 뿌요가 4개 이상 모이면 폭발시키는 함수
// 4개 이상 모여 폭발 성공하면 true, 실패하면 false 리턴
bool burst(int x, int y) {
    queue<Pair> q;
    vector<Pair> v;
    q.emplace(x, y);
    v.emplace_back(x, y);
    checked[x][y] = true;
    int count = 1;
    
    while(!q.empty()) {
        int curx = q.front().first;
        int cury = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];
            if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;
            if(field[nx][ny] == '.' || checked[nx][ny]
               || field[curx][cury] != field[nx][ny]) continue;
            
            count++;
            q.emplace(nx, ny);
            v.emplace_back(nx, ny);
            checked[nx][ny] = true;
        }
    }
    
    for(Pair p : v) checked[p.first][p.second] = false;
    
    if(count >= 4) {
        for(Pair p : v) {
            field[p.first][p.second] = '.';
        }
        return true;
    }
    else return false;
}

// 폭발 후 뿌요들을 아래로 떨어뜨리는 함수
void falling() {
    for(int i = 0; i < 6; i++) {
        queue<char> q;
        for(int j = 11; j >= 0; j--) {
            if(field[j][i] != '.') {
                q.push(field[j][i]);
                field[j][i] = '.';
            }
        }
        
        for(int j = 11; !q.empty(); j--) {
            field[j][i] = q.front();
            q.pop();
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    for(int i = 0; i < 12; i++) {
        for(int j = 0; j < 6; j++) {
            cin >> field[i][j];
        }
    }
    
    bool chain = false;
    
    do {
        chain = false;
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 6; j++) {
                if(field[i][j] == '.') continue;
                if(burst(i, j)) chain = true;
            }
        }
        
        falling();
        if(chain) ans++;
    } while(chain);
    
    cout << ans;
    return 0;
}