[11559] Puyo Puyo

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

11559번: Puyo Puyo

<문제>

행 : 12, 열 : 6으로 고정된 플러드필-시뮬레이션 문제이다.

모든 맵을 순차적으로 돌면서, 방문하지 않은 뿌요에 대해서 bfs를 진행한다.

영역의 넓이가 4이상이라면, vector에 행과 열을 저장해준다.

 

블럭을 터뜨리는건 단순히 해당 위치에 '.'을 넣어주면 되니 매우 간단하지만,

중력의 영향을 받도록 처리하는 부분에서 무언가 실수를 했는지 WA의 늪에 빠졌다.

로직을 싹 갈아엎고서야 AC를 받을 수 있었는데, 원래 작성했던 update함수는 아래의 형태였다.

void updateBlock(int idx) {
    for (auto& i : v[idx]) {
        a[i.first][i.second] = '.';
        for (int j = i.first - 1; j >= 1; j--) {
            a[j + 1][i.second] = a[j][i.second];
        }
    }
}

 

정확히 어디서 반례가 존재하는지를 찾지는 못했고,

중력의 영향을 받는 부분, 뿌요를 삭제하는 부분을 동시에 진행한 탓일수도 있겠다...

어쨋든 큐배열을 만들어서 한번에 업데이트하는 로직으로 갈아엎었다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
char a[30][30];
bool visited[30][30];
int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
vector<pair<int, int>> v[200];
int bfs(int sy, int sx, int idx) {
    queue<pair<int, int>> q;
    q.push({sy, sx});
    v[idx].clear();
    v[idx].push_back({sy, sx});
    visited[sy][sx] = true;
    int cnt = 1;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int y = cur.first + dy[i];
            int x = cur.second + dx[i];
            if (y < 1 || x < 1 || y > 12 || x > 6) continue;
            if (a[y][x] == a[sy][sx] && visited[y][x] == false) {
                q.push({y, x});
                v[idx].push_back({y, x});
                visited[y][x] = true;
                cnt++;
            }
        }
    }
    if (cnt < 4) v[idx].clear();
    return cnt;
}
void updateBlock(int idx) {
    for (auto& i : v[idx]) a[i.first][i.second] = '.';
    int i, j;
    queue<char> q[7];
    for (i = 1; i <= 6; i++) {
        for (j = 12; j >= 1; j--) {
            if (a[j][i] != '.') {
                q[i].push(a[j][i]);
            }
        }
    }
    for (i = 1; i <= 6; i++) {
        for (j = 12; j >= 1; j--) {
            if (!q[i].empty()) {
                a[j][i] = q[i].front();
                q[i].pop();
            } else {
                a[j][i] = '.';
            }
        }
    }
}
void printMap(void) {
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= 6; j++) {
            cout << a[i][j];
        }
        cout << '\n';
    }
}
int main(void) {
    int i, j, ans = 0;
    for (i = 0; i <= 14; i++) {
        for (j = 0; j <= 14; j++) {
            a[i][j] = '.';
        }
    }
    for (i = 1; i <= 12; i++)
        for (j = 1; j <= 6; j++) cin >> a[i][j];
    while (1) {
        bool flag = true;
        memset(visited, 0, sizeof(visited));
        int idx = 1;
        for (i = 1; i <= 12; i++) {
            for (j = 1; j <= 6; j++) {
                if (a[i][j] != '.' && visited[i][j] == false) {
                    int ret = bfs(i, j, idx);
                    if (ret >= 4) {
                        flag = false;
                        idx++;
                    }
                }
            }
        }
        if (flag) break;
        for (i = 1; i < idx; i++) {
            updateBlock(i);
            // cout << '\n';
            // printMap();
        }
        ans++;
    }
    cout << ans;
    return 0;
}