[백준 11559] Puyo Puyo, C++

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

11559번: Puyo Puyo

 본 문제는 2015 연세대학교 프로그래밍 경시대회 C번 문제다. 뿌요뿌요를 구현하는 문제다. 어렸을 때 많이했던 게임인데 문제로 만나니 참 반갑다. (못 풀었으면 안반가웠을 듯ㅎㅎ) 12 x 6 크기에 ' . '는 빈 공간이고 알파벳 대문자는 뿌요를 나타낸다. 

문제 해결 과정은 다음과 같다.

1. 인접한 4개의 뿌요가 같은 색이면 터진다.
2. 터진 뿌요 위에 다른 뿌요가 있으면 밑으로 내려온다.
3. 뿌요가 안터지면 프로그램을 끝낸다.

처음에 문제를 풀면서 뿌요가 터지고 바로 위에있는 뿌요를 밑으로 내렸다. 그러면 예제 TC는 맞지만 정답은 아니다. 즉, 전체를 탐색하면서 터질 뿌요를 정하고 한번에 터트려야 한다.

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <tuple>
 
using namespace std;
 
char map[13][7];
bool chk[13][7];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int main() {
    string s;
    for (int i = 0; i < 12; i++) {
        cin >> s;
        for (int j = 0; j < 6; j++) {
            map[i][j] = s[j];
        }
    }
    queue<tuple<char, int, int>> q;
    int ans = 0;
    vector<pair<int, int>> b;
    while (true) {
        bool flag = false;
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] == '.') continue;
                
                memset(chk, false, sizeof(chk));
                
                chk[i][j] = true;
                q.push(make_tuple(map[i][j], i, j));
 
                vector<pair<int, int>> v;
                v.push_back(make_pair(i, j));
 
                int cnt = 1;
                while (!q.empty()) {
                    char c;
                    int x, y;
                    tie(c, x, y) = q.front();
                    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) {
                            if (!chk[nx][ny] && map[nx][ny] == c) {
                                chk[nx][ny] = true;
                                q.push(make_tuple(c, nx, ny));
                                v.push_back(make_pair(nx, ny));
                                cnt += 1;
                            }
                        }
                    }
                }
                if (cnt >= 4) {
                    for (int k = 0; k < v.size(); k++) {
                        int x = v[k].first;
                        int y = v[k].second;
                        b.push_back(make_pair(x, y));
                    }
                }
            }
        }
        if (b.size() != 0) {
            flag = true;
            ans += 1;
            for (int k = 0; k < b.size(); k++) {
                map[b[k].first][b[k].second] = '.';
            }
            b.clear();
            for (int v = 0; v < 11; v++) {
                for (int u = 0; u < 6; u++) {
                    if (map[v][u] == '.') continue;
                    if (map[v+1][u] == '.') {
                        int index = 0;
                        while (v-index >= 0 && map[v-index][u] != '.') {
                            map[v-index + 1][u] = map[v-index][u];
                            index += 1;
                        }
                        map[v-index+1][u] = '.';
                    }
                }
            }
        }
        if (!flag) break;
    }
    printf("%d\n", ans);
}