[알고리즘] 백준 11559 - Puyo Puyo (C++)

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

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

char Arr[12][6];
bool Check[12][6];
int Dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
int tmp, Ans;
bool flag;

vector<pair<int, int>> T, V;

void print(){
    for(int i=0; i<12; i++){
        for(int j=0; j<6; j++){
            cout << Arr[i][j];
        }
        cout << "\n";
    }
    return;
}

void solve(int y, int x){
    for(int d=0; d<4; d++){
        int ny = y + Dir[d][0];
        int nx = x + Dir[d][1];

        if(ny < 0 || nx < 0 || ny >= 12 || nx >= 6){
            continue;
        }
        if(Arr[ny][nx] == '.' || Check[ny][nx] == true || Arr[y][x] != Arr[ny][nx]){
            continue;
        }

        tmp++;
        Check[ny][nx] = true;
        T.push_back({ny, nx});
        solve(ny, nx);
    }
    return;
}

int main(){
    for(int i=0; i<12; i++){
        cin >> Arr[i];
    }

    while(true){
        flag = false;
        memset(Check, false, sizeof(Check));
        V.clear();

        for(int i=0; i<12; i++){
            for(int j=0; j<6; j++){
                if(Arr[i][j] == '.' || Check[i][j] == true){
                    continue;
                }
                tmp = 1;
                T.push_back({i, j});
                Check[i][j] = true;
                solve(i, j);

                if(tmp >= 4){
                    flag = true;
                    for(int k=0; k<T.size(); k++){
                        V.push_back(T[k]);
                    }
                }
                T.clear();
            }
        }

        for(int i=0; i<V.size(); i++){
            int y = V[i].first;
            int x = V[i].second;
            Arr[y][x] = '.';
        }

        for(int i=10; i>=0; i--){
            for(int j=0; j<6; j++){
                if(Arr[i][j] == '.'){
                    continue;
                }

                int t = i;

                while(true){
                    if(t == 11 || Arr[t + 1][j] != '.'){
                        break;
                    }

                    Arr[t + 1][j] = Arr[t][j];
                    Arr[t][j] = '.';
                    t++;
                }
            }
        }

        if(flag == true){
            Ans++;
        }
        else{
            break;
        }
    }
    cout << Ans << "\n";
    return 0;
}