[백준/BOJ] 11559번 Puyo Puyo (C++)

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

BFS + 시뮬레이션(구현) 문제

Puyo가 제거되고 난 후 중력 처리를 해주는 부분을 구현하는 데 애를 먹은 문제입니다. 제거 될 Puyo를 벡터에 저장한 후, 이를 열 기준 오름차순으로 정렬하고 열 마다 한 행씩 뒤에서 앞으로 값을 넣어주는 것이 문제 해결의 포인트입니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

char map[12][6];
bool visit[12][6];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int chain;

// 열 기준으로 오름차순 정렬 함수
int cmp(const pair<int, int> a, const pair<int, int> b) {
    // 열의 값이 같다면 행 기준 오름차순
    if(a.second == b.second) {
        return a.first < b.first;
    }
    // 열 기준 오름차순
    return a.second < b.second;
}

void doPuyo() {
    while(1) {
        queue<pair<int, int > > q;
        vector<pair<int, int > > v; // 없어질 뿌요를 저장할 벡터
        memset(visit, false, sizeof(visit));
        
        for(int i = 11; i >= 0; i--) {
            for(int j = 0; j < 6; j++) {
                if(map[i][j] == '.') continue;
                if(map[i][j] != '.') {
                    char pivot = map[i][j];
                    queue<pair<int, int > > tmp; // 탐색중에 없어질 뿌요를 임시 저장하는 큐
                    q.push({i, j});
                    visit[i][j] = true;
                    
                    while(!q.empty()) {
                        int x = q.front().first;
                        int y = q.front().second;
                        tmp.push({x, y});    
                        q.pop();
                        
                        for(int k = 0; k < 4; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;
                            if(visit[nx][ny] || map[nx][ny] != pivot) continue;
                            q.push({nx, ny});
                            visit[nx][ny] = true;
                        }
                    }
                    
                    // 같은 색의 뿌요가 4개 이상인 경우, tmp의 원소를 v에 전부 옮김
                    if(tmp.size() >= 4) {
                        while(!tmp.empty()) {
                            v.push_back(tmp.front());
                            tmp.pop();
                        }
                    }
                }
            }
        }
        
        // 한 턴을 진행한 후 제거된 뿌요가 있는 경우, 중력 처리가 필요
        if(!v.empty()) {
            sort(v.begin(), v.end(), cmp);
            // 열 마다 중력처리를 해줌(현재 열의 뒤의 행 원소를 앞의 행으로)
            for(int i = 0; i < v.size(); i++) {
                for(int j = v[i].first; j > 0; j--) {
                    map[j][v[i].second] = map[j - 1][v[i].second];
                }
                // 마지막 행은 뒤의 원소가 없으므로 따로 처리
                map[0][v[i].second] = '.';
            }
            chain++; // 연쇄 증가
        }
        // 제거된 뿌요가 없는 경우, 중력 처리가 필요 없으므로 바로 종료
        if(v.empty()) break;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    for(int i = 0; i < 12; i++) {
        for(int j = 0; j < 6; j++) {
            cin>>map[i][j];
        }
    }
    
    doPuyo();
    cout<<chain;
}