[Algorithm/C++17] 백준 11559 Puyo Puyo

문제

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

11559번: Puyo Puyo

풀이 방법

예전에 유명했던 테트리스 비슷한 게임인 뿌요뿌요 관련된 문제이다. 뿌요뿌요는 같은 색깔이 4개 이상 연결되어 있으면 터지며, 터진 후에 위에 있던 뿌요들이 아래로 내려오면서 연결되면 또 터진다. 이를 연쇄라고 한다.

 

필드의 정보가 주어졌을때 연쇄가 얼마나 일어나는지 계산하는 문제이다. 

1. 4개 이상 연결되어 있는 뿌요를 찾는다.
2. 터뜨린다. (빈 칸으로 만든다)
3. 위에 있던 뿌요들을 아래로 내린다.

가 몇 번 반복되는지 계산하면 된다. 아래 코드에서는 1과 2를 하나의 PopPuyo 함수로, 3을 Collapse 함수로 만들었다.

 

연결되어있는 뿌요를 찾는 것은 BFS를 사용하면 쉽게 판별할 수 있다. 하지만 아래로 내리는 로직이 생각해내기가 좀 어렵다. 왜냐하면 다음과 같은 케이스들이 있기 때문이다.

• 뿌요 - 빈칸 - 뿌요
• 빈칸 - 뿌요
• 뿌요 - 빈칸

뿌요와 빈 칸 인덱스를 일일이 찾아서 처리해주기가 번거로울 것 같아 그냥 큐에 담아서 담아진대로 일렬로 배치하는 방식을 사용했다.

 

코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
bool PopPuyo(vector<vector<char>>& field)
{
    bool popped = false;
    vector<vector<bool>> visited(12, vector<bool>(6, false));
    queue<pair<int, int>> q;
    for(int i=11; i>=0; i--)
    {
        for(int j=0; j<6; j++)
        {
            // 같은 색 뿌요 연결
            if(!visited[i][j] && field[i][j] != '.')
            {
                vector<pair<int, int>> puyo;
                char color = field[i][j];
                q.push({i,j});
                visited[i][j] = true;
                puyo.push_back({i,j});
                while(!q.empty())
                {
                    auto cur = q.front();
                    q.pop();
                    int y = cur.first;
                    int x = cur.second;
                    for(int k=0; k<4; k++)
                    {
                        int ny = y+dy[k];
                        int nx = x+dx[k];
                        if(ny < 0 || ny >= 12 || nx < 0 || nx >= 6) continue;
                        if(field[ny][nx] != color || visited[ny][nx]) continue;
                        q.push({ny,nx});
                        visited[ny][nx] = true;
                        puyo.push_back({ny,nx});
                    }
                }
                // 연결된 뿌요가 4개이상이면 터뜨림
                if(puyo.size() >= 4)
                {
                	popped = true;
                    for(const auto& t : puyo)
                    {
                        int y = t.first;
                        int x = t.second;
                        field[y][x] = '.';
                    }
                }
            }
        }
    }
    return popped;
}

void Collapse(vector<vector<char>>& field)
{
    for(int i=0; i<6; i++)
    {
        queue<char> q;
        for(int j=11; j>=0; j--)
        {
            if(field[j][i] != '.') q.push(field[j][i]);
        }
        for(int j=11; j>=0; j--)
        {
            if(q.empty()) field[j][i] = '.';
            else
            {
                field[j][i] = q.front();
                q.pop();
            }
        }
    }
}

int main()
{
    vector<vector<char>> field(12, vector<char>(6));
    for(int i=0; i<12; i++)
    {
        for(int j=0; j<6; j++)
        {
            scanf(" %1c", &field[i][j]);
        }
    }
    
    int answer = 0;
    while(PopPuyo(field))
    {
        Collapse(field);
        answer++;
    }
    
    printf("%d", answer);
    return 0;
}

고찰

연결되어 있는 뿌요가 몇 번 터지는지 계산하는 문제인줄 알고 삽질했었다. 문제를 잘 읽자...

비슷한 문제로는 https://www.acmicpc.net/problem/12100 가 있다.

 

뿌요뿌요를 풀었다면 이 문제도 풀 수 있을 것이다.

12100번: 2048 (Easy)

 

여담으로 테트리스는 유명한데 뿌요뿌요는 그렇지 않은 것 같다.

둘 다 고인물 게임이면서 뭔가 쌓아놓고 터뜨린다는 공통점이 있어서 그런지 콜라보한 게임도 있다.

심심하거나 머리 식히는 용으로 한번 봐보자!

유튜브