[백준]PuyoPuyo

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

11559번: Puyo Puyo

flag를 사용하는 문제의 경우 dfs보다 bfs가 적합한것 같다. dfs의 경우는 재귀구조로 계속 flag정보가 변한다. 최종 원하는 함수를 실행하고 바로 종료해주기가 까다롭다. --> 종료시점의 부분에서 항상 주의해야 한다!!!!

또한, flag를 설정할 때 else false를 해주면 이미 true를 발견했지만 다시 false로 정보가 갱신되는 문제에 주의해야한다.

즉, true가 한번이라도 있으면 true로 바꾸고 나머지 경우에 대해서는 false로 갱신을 하면 안된다는 것.

큐나 벡터를 통해 원소들의 값을 쭈루룩 옮기는 것도 편리한것 같다.

 

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
 
struct INFO {
    int r, c;
};
 
bool flag = false;
char map[12][6];
bool isV[12][6];
queue<INFO> q, q_block;
vector<char> v;
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
 
void bfs(int r, int c, char val) {
    isV[r][c] = true;
    q.push({ r,c });
    q_block.push({ r,c });
    while (!q.empty()) {
        int rr = q.front().r, cc = q.front().c; q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = rr + dr[i], nc = cc + dc[i];
            if (nr < 0 || nc < 0 || nr >= 12 || nc >= 6) continue;
            if (!isV[nr][nc] && map[nr][nc] == val) {
                isV[nr][nc] = true;
                q.push({ nr,nc });
                q_block.push({ nr,nc });
            }
        }
    }
    if (q_block.size() >= 4) {
        flag = true;
        while (!q_block.empty()) {
            int nr = q_block.front().r, nc = q_block.front().c; q_block.pop();
            map[nr][nc] = '.';
        }
    }
    else { //여기서 flag=false를 하는 실수를 했었음.
        while (!q_block.empty()) q_block.pop();
    }
}
 
void fall() {
    for (int c = 0; c < 6; c++) {
        for (int r = 0; r < 12; r++) {
            if (map[r][c] != '.') {
                v.push_back(map[r][c]);
                map[r][c] = '.';
            }
        }
        for (int r = 0; r < v.size(); r++) {
            map[r][c] = v[r];
        }
        v.clear();
    }
}
 
void solve() {
    int cnt = 0;
    while (1) {
        flag = false;
        memset(isV, false, sizeof(isV));
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (!isV[i][j] && map[i][j] != '.') {
                    bfs(i, j, map[i][j]);
                }
            }
        }
        if (flag) cnt++;
        else break;
        fall();
    }
    printf("%d\n", cnt);
}
 
int main()
{
    for (int i = 11; i >= 0; i--) {
        for (int j = 0; j < 6; j++) {
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}