[BOJ][C++] 백준 11559번: Puyo Puyo

문제

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

 

문제 이해

뿌요뿌요 게임 중, 현재 주어진 필드에서 몇연쇄가 되는지 구한다.

 

뿌요뿌요 룰

- 뿌요의 색은 R, G, B, Y가 있다.
- 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 그 뿌요들이 모두 없어진다. 이것을 1연쇄라고 한다.
- 뿌요는 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요가 없어지면, 똑같이 아래로 떨어진다.
- 아래로 떨어지고 나서 다시 뿌요가 터지면 1연쇄가 늘어난다.
🚨 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터진다. 여러 그룹이 터지더라도 1연쇄가 추가된다.

 

 

문제 풀이

🔍 접근

연결된 같은 색의 뿌요를 찾는다는 관점에서 DFS, BFS 탐색을 떠올릴 수 있다.

탐색 후 연결된 뿌요가 4개 이상이면 터트리고, 다시 탐색한다.

 

❔ DFS보다 BFS를 선택한 이유

1. 그룹 저장이 쉬움
   BFS는 탐색 과정에서 큐에 넣은 좌표들을 그대로 모아서
   vector<pair<int, int>> group처럼 방문한 좌표를 쉽게 저장할 수 있음.
2. 재귀 깊이 제한 없음
   DFS에서 최악의 경우, 뿌요 72개가 연결되어 있다면 재귀 함수 호출 72번 됨.
3. 여러 그룹 동시 처리에 유리
   BFS는 각 탐색마다 그룹 단위로 분리하여 처리하기 쉬워서,
   한 턴에 여러 그룹이 동시에 터지는 게임 로직에 적합함.

💡 BFS

1. 연결된 같은 색의 뿌요를 BFS를 통해 찾는다.
   탐색하면서 터트릴 뿌요의 좌표와 연결된 뿌요의 개수를 저장한다.
2. 연결된 뿌요가 4개 이상이면 터트린다.
   터트릴 뿌요의 좌표에 .을 삽입한다.
3. 연쇄가 일어난 후의 필드로 갱신한다.
   각 열의 뿌요를 모아 아래에서 부터 채워준다.
4. 1 ~ 3의 과정을 터트릴 뿌요가 없을 때까지 반복한다.
   BFS 탐색 후 연결된 뿌요의 개수가 4 이상이면 true를 반환하여 flag 변수에 표시한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

const int MAX_ROW = 12;
const int MAX_COL = 6;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void update_field(vector<vector<char>> &field) {
    for (int i = 0; i < MAX_COL; i++) {
        vector<char> puyo;
        for (int j = 0; j < MAX_ROW; j++) {
            if (field[j][i] == '.')
                continue;
            puyo.push_back(field[j][i]);
        }
        for (int j = MAX_ROW - 1; j >= 0; j--) {
            if (puyo.empty()) {
                field[j][i] = '.';
            } else {
                field[j][i] = puyo.back();
                puyo.pop_back();
            }
        }
    }
}

bool bfs(int r, int c, vector<vector<char>> &field) {
    queue<pii> q;
    vector<pii> exploded;
    vector<vector<bool> > visited(MAX_ROW, vector<bool>(MAX_COL, false));
    int cnt = 1;
    char color = field[r][c];

    q.push({r, c});
    exploded.push_back({r, c});
    visited[r][c] = true;
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= MAX_ROW || nc < 0 || nc >= MAX_COL
                || field[nr][nc] != color || visited[nr][nc])
                continue;
            visited[nr][nc] = true;
            q.push({nr, nc});
            exploded.push_back({nr, nc});
            cnt++;
        }
    }

    if (cnt < 4)
        return false;

    for (auto i: exploded)
        field[i.first][i.second] = '.';
    return true;
}

int solution(vector<vector<char>> &field) {
    int ans = 0;

    while (true) {
        bool flag = false;
        for (int i = 0; i < MAX_ROW; i++) {
            for (int j = 0; j < MAX_COL; j++) {
                if (field[i][j] == '.')
                    continue;
                if (bfs(i, j, field))
                    flag = true;
            }
        }
        if (!flag)
            break;
        update_field(field);
        ans++;
    }
    return ans;
}

int main() {
    vector<vector<char> > field(MAX_ROW, vector<char>(MAX_COL, '.'));

    // 입력
    for (int i = 0; i < MAX_ROW; i++) {
        for (int j = 0; j < MAX_COL; j++) {
            cin >> field[i][j];
        }
    }

    // 출력
    cout << solution(field);

    return 0;
}