[BOJ-11559]Puyo Puyo

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

[풀이방법]

DFS 탐색을 이용해서 풀었다. 물론 BFS 로 풀어도 풀린다.

dfs로 전역변수인 py_count (인접한 같은 것이 몇개가 같은 것이 있는지 판단하는 count)를 확인한다.

이후

py_count가 4이상이라면 해당 블럭을 지워주는 del_dfs를 실시한다. 

매 경우마다 진행하며, 블럭을 지우는 경우가 없다면 게임을 끝낸다. 

게임이 끝나지 않는 경우 블럭을 아래로 내려주고, 

게임진행횟수를 +1 한다.

[C++11]

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
 
const int dr[] = { 0,0,-1,1 };
const int dc[] = { -1,1, 0,0 };
const int row = 12;
const int col = 6;
int ans;
char im[row][col];
int vis[row][col];
int py_count;
 
void down() {
    for (int c = 0; c < col; c++) {
        for (int r = row-1; r >= 0; r--) {
            if (im[r][c] == '.') {
                for (int tr = r - 1; tr >= 0; tr--) {
                    if (im[tr][c] != '.') {
                        im[r][c] = im[tr][c];
                        im[tr][c] = '.';
                        break;
                    }
                }
            }
        }
    }
}
 
int mx2(int a, int b) { return (a > b) ? a : b; }
int mn2(int a, int b) { return (a > b) ? b : a; }
 
int dfs(int r, int c, char RGB) {
    int ret = 0;
    if (im[r][c] == RGB) ret = vis[r][c];
    else if(im[r][c] != RGB) return ret = 0;
    
    for (int i = 0; i < 4; i++) {
        int tr = r + dr[i];
        int tc = c + dc[i];
        if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
        if (vis[tr][tc]) continue;
        if (im[tr][tc] != RGB) continue;
        vis[tr][tc] = ++py_count;
        ret = mx2(ret,dfs(tr, tc, RGB));        
    }
    return ret;
}
 
void del_dfs(int r, int c, char RGB) {
    if (im[r][c] == RGB) im[r][c] = '.';
    else if (im[r][c] != RGB) return;
 
    for (int i = 0; i < 4; i++) {
        int tr = r + dr[i];
        int tc = c + dc[i];
        if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
        if (im[tr][tc] != RGB) continue;
        del_dfs(tr, tc, RGB);
    }
}
 
int main() {
    for (int r = 0; r < row; r++) {
        scanf("%s", im[r]);
    } // input
    
    while (1) {
        int ret = 0;        
        memset(vis, 0, sizeof(vis));
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (im[r][c] == '.') continue;        
                vis[r][c] = py_count = 1;
                ret = mx2(dfs(r, c, im[r][c]),ret);
                if (py_count >= 4) del_dfs(r, c, im[r][c]);
            }
        }
        if (ret < 4) break;
        down();
        ans++;
    }
    printf("%d\n", ans);    
    
    return 0;
}