[BOJ / C++] Puyo Puyo (시뮬레이션, BFS)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool checkPuyo(vector<vector<char>>& board, vector<vector<bool>>& vis, int x, int y, int r, int c) {
    queue<pair<int, int>> Q;
    vector<pair<int, int>> puyoCoord;
    Q.push({x, y});
    puyoCoord.push_back({x, y});
    vis[x][y] = true;

    int cnt = 1;
    char checkChar = board[x][y];
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        int cx, cy;
        tie(cx, cy) = cur;
        for (int dir = 0; dir < 4; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            if (board[nx][ny] != checkChar || vis[nx][ny] == true) continue;
            Q.push({nx, ny});
            puyoCoord.push_back({nx, ny});
            vis[nx][ny] = true;
            cnt++;
        }
    }

    if (cnt >= 4) {
        for (auto cur: puyoCoord) {
            int cx = cur.first, cy = cur.second;
            board[cx][cy] = '.';
        }
        return true;
    }
    else {
        return false;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int r = 12, c = 6;
    vector<vector<char>> board(r, vector<char>(c));
    
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }

    int puyoCnt = 0;

    while (true) {
        vector<vector<bool>> vis(r, vector<bool>(c, false));
        bool puyo = false;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] == '.' || vis[i][j]) continue;
                
                if (checkPuyo(board, vis, i, j, r, c) == true) {
                    puyo = true;
                }
            }
        }

        // puyo check
        if (puyo == true) puyoCnt++;
        else break;
        
        
        // board down update
        for (int j = 0; j < c; j++) {
            vector<char> tmp(r, '.');
            int idx = 0;
            for (int i = r-1; i >= 0; i--) {
                if (board[i][j] != '.') {
                    tmp[idx] = board[i][j];
                    idx++;
                }
            }
            
            for (int i = r-1; i >= 0; i--) {
                board[i][j] = tmp[r-1-i];
            }
        }
        
    }
    cout << puyoCnt << '\n';
}

 

 

2. 분석

구현해야할 부분은 크게 3가지이다.

(1) board를 순회하면서 뿌요가 될 수 있는 부분이 있는지(4개 연결 부분) 찾기

(2) 해당 뿌요 부분을 '.'으로 터뜨리기

(3) 뿌요로 터뜨린 이후 중력에 의해 바닥에 떨구기

 

(1), (2)를 checkPuyo 함수에서 구현했다. BFS는 한번만 돌고 해당 좌표들을 vector<pair<int, int>> puyoCoord에 저장해뒀다가 나중에 cnt >= 4 면 해당 뿌요들을 터드리는 방식으로 구현한다. 처음에 BFS를 두번씩 돌아야하나 했는데 좌표들을 저장했다가 판단한 후 터뜨리면 된다.

중력에 의해 바닥으로 터뜨리는 부분은 각 column에 대해 tmp 배열로 업데이트 배열을 만들어 어떻게 변할지 변하는 column 상태를 저장하고 다시 board에 업데이트 해주는 방식으로 해주면 편하다.

 

3. 시간복잡도

row와 column이 12 x 6으로 고정이라 웬만하면 시간제한 1초내에 통과할 것을 알 수 있다. 시간복잡도는 각 뿌요 스테이지마다 한번씩 board를 순회하므로 12 * 6 * 뿌요 횟수로 계산하면 된다.