백준11559 - Puyo Puyo

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

11559번: Puyo Puyo

BFS를 이용하여 해결한 문제이다. 블록이 상하좌우로 4개가 연결되면 블록이 사라진다. 또한 동시 다발로 사라지는 블록은 1회로 세야 한다. 이점만 주의한다면 해결할 수 있다. 그리고 블록은 밑으로만 내려온다고 문제에서 주어졌기 때문에 2차원 배열을 탐색할 시에 아래부터 탐색하여 위로 올라가는 방법을 써야지 빈 공간을 매꿀 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define WIDTH 7
#define HEIGHT 13
using namespace std;

bool visit[HEIGHT][WIDTH] = { false, };
char mat[HEIGHT][WIDTH];
int cnt = 0;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

vector<queue<pair<int,int>>> v;

void bomb(int x, int y) {
    char c = mat[x][y];
    queue<pair<int,int>> q;
    queue<pair<int,int>> temp;
    
    q.push(pair<int,int>(x, y));
    temp.push(pair<int,int>(x, y));
    visit[x][y] = true;
    
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            //유효 범위이고 방문 안한 공간이고 시작하는 색깔이랑 같은 색이면
            if(1 <= nx && nx < HEIGHT && 1 <= ny && ny < WIDTH && !visit[nx][ny] && mat[nx][ny] == c) {
                q.push(pair<int,int>(nx, ny));
                temp.push(pair<int,int>(nx, ny));
                visit[nx][ny] = true;
            }
        }
    }
    
    if(temp.size() >= 4) {
        v.push_back(temp);
    }
}

int main() {
    
    for(int i = 1; i < HEIGHT; i++) {
        for(int j = 1; j < WIDTH; j++) {
            cin >> mat[i][j];
        }
    }
    
    while(1) {
        v.clear();
        memset(visit, false, sizeof(bool) * HEIGHT * WIDTH);
        for(int i = 1; i < HEIGHT; i++) {
            for(int j = 1; j < WIDTH; j++) {
                if(mat[i][j] != '.' && !visit[i][j]) {
                    bomb(i, j);
                }
            }
        }
        
        if(v.size() == 0) {
            break;
        }
        else {
            queue<pair<int,int>> down;
            for(int i = 0; i < v.size(); i++) {
                while(!v[i].empty()) {
                    int x = v[i].front().first;
                    int y = v[i].front().second;
                    v[i].pop();
                    
                    mat[x][y] = '.';
                }
            }
            
            for(int i = 1; i < WIDTH; i++) {
                for(int j = HEIGHT - 1; j >= 1; j--) {
                    if(mat[j][i] != '.') {
                        down.push(pair<int,int>(j, i));
                    }
                }
            }
            
            while(!down.empty()) {
                int x = down.front().first;
                int y = down.front().second;
                down.pop();
                
                for(int i = HEIGHT - 1; i >= x; i--) {
                    if(mat[i][y] == '.') {
                        mat[i][y] = mat[x][y];
                        mat[x][y] = '.';
                        break;
                    }
                }
            }
            cnt++;
        }
    }
    
    cout << cnt;
}