[BOJ] 11559. Puyo Puyo

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

11559번: Puyo Puyo

시뮬레이션 카테고리에 넣었지만 BFS도 이용하는 문제이다.

BFS는 상하좌우로 연결되어 있는 같은 색의 뿌요를 찾기 위해 사용한다.

 

 

먼저 연쇄가 몇 번 일어났는지를 알아내야 하는 문제이기 때문에 연쇄가 일어나지 않을 때까지 터뜨리기를 반복해야한다.

 

 

각 반복에서는 뿌요가 있는 모든 칸에 대해서 BFS탐색을 통해 상하좌우로 연결된 같은 색의 뿌요가 네 개 이상 있는지 체크해준다. 있다면 해당 칸의 뿌요들을 터뜨려주고(.으로 만들어 준다) 연쇄가 발생했다는 뜻으로 true를 리턴한다.

문제 조건에 따라 여러 그룹의 뿌요가 터졌더라도 연쇄는 한 번 일어난 걸로 간주한다.

예를 들어, 전체 칸을 탐색할 때 R이 4개 이상 모여있었고 다른 곳에서 G가 4개이상 모여있어서 두 그룹이 터졌다고 해도 같은 턴에 터지는 애들은 한번 일어난 걸로 count 해준다.

 

 

모든 뿌요에 대해서 탐색을 해줬는데 flag가 false라면 (한 번도 연쇄가 발생하지 않았다면) 반복문을 break 해주고 정답을 출력해주면 된다.

 

flag가 true라면(연쇄가 적어도 한 번 이상 발생했다면) 떠있는 뿌요들을 바닥에 내려주고 연쇄가 일어난 횟수(정답)를 증가시킨다.

 

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
 
char map[12][6];
int check[12][6];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans;
 
void move() {
    for (int j = 0; j < 6; j++) {
        for (int i = 11; i >= 0; i--) {
            if (map[i][j] != '.') continue;
 
            //빈 칸(.)을 찾았으므로 위에 떠있는 애를 찾는다.
            bool flag = false;
            for (int k = i - 1; k >= 0; k--) {
                
                //떠있는애 발견
                if (map[k][j] != '.') {
                    //내려준다.
                    map[i][j] = map[k][j];
                    map[k][j] = '.';
                    flag = true;
                    break;
                }
            }
 
            //위에 떠있는게 없으면 다음 열을 검사한다.
            if (!flag) {
                break;
            }
        }
    }
}
 
bool bfs(int x, int y) {
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    
    q.push(make_pair(x, y));
    check[x][y] = true;
    int cnt = 1;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            //범위 체크
            if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue;
            //방문 체크
            if (check[nx][ny]) continue;
            //같은 색인지 체크
            if (map[nx][ny] != map[x][y]) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
            cnt++;
        }
    }
 
 
    //같은 색의 뿌요가 4개이상 존재하면 모두 터진다.
    if (cnt >= 4) {
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (check[i][j]) map[i][j] = '.';
            }
        }
        
 
        return true;
    }
    else return false;
}
 
void solve() {
    
    
    while (true) {
 
        bool flag = false;
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] == '.') continue; //빈칸
 
                //같은 색의 뿌요들이 4개이상 모여있어서 터지는지 검사
                if (bfs(i, j)) {
                    flag = true;
                }
 
            }
        }
 
        //더 이상 터질게 없다.
        if (!flag) break;
        else {
            //터졌으면 중력에 의해 뿌요들이 아래로 떨어진다.
            move();
 
            ans++;
        }
 
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    string s;
    for (int i = 0; i < 12; i++) {
        cin >> s;
        for (int j = 0; j < 6; j++) {
            map[i][j] = s[j];
        }
    }
 
    solve();
 
 
    cout << ans << '\n';
    return 0;
}