(C++) [백준 11559번] Puyo Puyo

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

11559번: Puyo Puyo

시뮬레이션 + BFS를 이용하는 문제이다.

12*6 크기의 필드에 R,G,B,P,Y 총 5개의 뿌요와 빈 공간을 나타내는 '.' 문자까지 총 6개의 문자가 주어질 때 가능한 연쇄의 횟수를 출력하면 된다.

특정 뿌요를 기준으로 같은 색의 뿌요가 4개이상 상하좌우로 연결되어있는 경우 터지는데, 이를 연쇄라고 한다.

터질 수 있는 뿌요가 여러 개라면 한 번에 터져야 하고, 한 번에 터지는 경우는 1연쇄로 취급한다.

또한 뿌요는 중력의 영향을 받기 때문에 빈 공간이나 가장 아래에 놓일 때 까지 쭉 위에서 아래로 떨어진다.

 

뿌요뿌요를 해본 적은 없지만 하는 걸 여러 번 본 적이 있어서 수월하게 풀었다. 그리고 이번 문제를 통해 뿌요뿌요의 연쇄 조건을 알게 되었다.

나는 다음과 같은 방법을 생각해서 풀었다.

1) 뿌요가 있는 배열의 [0][0]부터 시작하면서 '.'가 아닌 경우 BFS를 수행하고, BFS에서 한 뿌요에 대해 탐색한 횟수가 4 이상인 경우 해당 뿌요를 터트리고, 연쇄가 일어남을 표시하기 위해 flag를 true로 만든다.

2) 1번을 [r-1][c-1]까지 반복하고, flag가 true인 경우 결과값에 1을 더한다.

3) 뿌요를 가장 아래쪽으로 내린다. -> 이는 백준 12100번 2048 (Easy) 문제나, 백준 15683번 감시 문제에서처럼

배열을 미는 것과 같다고 생각해서 쉽게 풀었다. 잠시 설명하자면 다음과 같은 방법이다.

  1: 원본 배열과 옮길 배열을 준비하고, idx라는 옮길 배열의 인덱스를 담을 배열 1개를 따로 준비한다.

  2: 원본 배열의 값이 '.'가 아닌 경우(뿌요가 있는 경우) 옮길 배열에 담고 인덱스를 1 추가한다(Array2[idx++] = Array1[i])

  3: 1,2번을 전체 배열에 대해서 반복한다.

4) *중요! 2번의 flag가 true인 경우 결과값에 1을 추가하고, BFS에 사용했던 checked 배열을 초기화한다. flag가 false라면 종료한다. 

 

내가 생각한 시간 복잡도는 다음과 같다.

먼저 배열 전체에 대해서 BFS를 수행하므로 12*6, 가장 아래쪽으로 내리는 과정에서 12*6만큼 필요하고, 최대 일어날 수 있는 연쇄의 횟수는 72/4 = 18연쇄이므로 총 18번 수행할 수 있다. 따라서 총 시간 복잡도는 다음과 같다. (틀릴 수 있음!)

BFS를 수행하는데 (12 * 6), 배열을 내릴 때 (12* 6), 이를 18번 = 18(12 * 6 * 12 * 6) = 93312

여기서 핵심 함수는 배열 전체에 대해서 BFS를 수행하는 find(), 뿌요를 아래쪽으로 내리는 move()이다.

 

1) find()

 

bool find()
{
    bool flag = false;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (!visited[i][j] && board[i][j] != '.')
            {
                q.push({ i,j });
                BFS(board[i][j]);
            }
            if (v.size() >= 4)
            {
                for (int k = 0; k < v.size(); k++)
                {
                    board[v[k].X][v[k].Y] = '.';
                    flag = true;
                }
            }
            v.clear();
        }
    }
 
    return flag;
}

아직 방문하지 않은 정점이고, 뿌요인 경우에 해당 정점에 대해 BFS를 수행한다.

BFS에서 방문한 정점은 v에 추가하는데, 이 v가 4 이상인 경우에는 연쇄가 가능하므로 해당 뿌요들을 터트리고 flag를 true로 만든다. 이후 해당 정점은 '.'로 바꿔준다.

 

2) move()

 
void move()
{
    int idx = 0;
    char board2[R];
 
    for (int i = 0; i < C; i++)
    {
        fill(board2, board2 + R, '.');
        idx = 0;
        for (int j = 0; j < R; j++)
        {
            if (board[j][i] != '.')
                board2[idx++] = board[j][i];
        }
 
        for (int j = R - 1; j >= 0; j--)
        {
            if (idx <= 0) board[j][i] = '.';
            else
            board[j][i] = board2[--idx];
        }
    }
 
}

인덱스 idx와 board2를 이용하는데, 2번째 for (int j = R - 1; j >= 0; j--) 반복문이 조금 헷갈릴 수 있다.

처음에 idx를 이용해 추가할 때 0부터 추가했는데 보드의 가장 아래쪽부터 값을 복사해야 하기 때문에 가장 아래에서부터 시작하면 된다.

 

아래는 전체 코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define R 12
#define C 6
#define X first
#define Y second
char board[R][C];
bool visited[R][C];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int res;
queue <pair<int, int>> q;
vector <pair<int, int>> v;
void BFS(char now)
{
    while (!q.empty())
    {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C || visited[nx][ny]) continue;
            if (board[nx][ny] != now) continue;
            q.push({ nx,ny });
            v.push_back({ nx,ny });
            visited[nx][ny] = true;
        }
    }
}
bool find()
{
    bool flag = false;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (!visited[i][j] && board[i][j] != '.')
            {
                q.push({ i,j });
                BFS(board[i][j]);
            }
            if (v.size() >= 4)
            {
                for (int k = 0; k < v.size(); k++)
                {
                    board[v[k].X][v[k].Y] = '.';
                    flag = true;
                }
            }
            v.clear();
        }
    }
 
    return flag;
}
void move()
{
    int idx = 0;
    char board2[R];
 
    for (int i = 0; i < C; i++)
    {
        fill(board2, board2 + R, '.');
        idx = 0;
        for (int j = 0; j < R; j++)
        {
            if (board[j][i] != '.')
                board2[idx++] = board[j][i];
        }
 
        for (int j = R - 1; j >= 0; j--)
        {
            if (idx <= 0) board[j][i] = '.';
            else
            board[j][i] = board2[--idx];
        }
    }
 
}
void input()
{
    string str = "";
    for (int i = 0; i < R; i++)
    {
        cin >> str;
        for (int j = 0; j < C; j++)
            board[i][j] = str[j];
    }
 
}
int main()
{
    cin.tie(0); ios::sync_with_stdio(0);
    bool flag;
    input();
    while (true)
    {
        flag = find();
        move();
        if (flag == false) break;
        res++;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                visited[i][j] = false;
    }
    cout << res;
}