[BOJ] C++ 11559: Puyo Puyo - BFS로 구현한 시뮬레이션

11559번: Puyo Puyo

예제

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

ans : 3

---

먼저 맵의 크기가 72로 매우 작고, 한 번의 연쇄 작용 후 맵을 갱신하지 않고는 다시 연쇄 작용을 하기 매우 힘들다. 따라서 연쇄 작용 후 맵 갱신을 하는 방식으로 기초를 잡았다. 연쇄 작용은 BFS로 빠른 시간 내에 구현할 수 있을 것 같고, 맵 갱신 또한 72개의 데이터만 연산하면서 구현할 수 있을 것 같아서 바로 구현했다. 시간복잡도는 모든 점에 대해 bfs를 돌린다고 생각하면 O(72^72)이므로 충분히 가능하다. 심지어 모든 점에 대해 bfs를 돌릴 일은 아마 없을 것이다. 추가로 주의해야 할 점이 맵 갱신 전에 일어난 모든 연쇄는 1번으로 카운팅 한다. 

 

필수적으로 구현해야할 사항은 다음과 같다.

1. 연쇄 가능한 점 찾기
2. 연쇄시키기
   1, 2번은 BFS 하나의 함수로 구현이 가능할 것 같다. 일단 따로 구현할 생각을 하고 (a, b)의 점이 연쇄 가능한지 판단하는 것부터 구현해 보자.
3. 맵 갱신
   맵 갱신 부분은 전에 푼 2048 문제에서 거의 똑같은 부분을 구현해 본 적 있어서 쉽게 구현했다. 이 부분이 어렵다면 아래 글을 참고하자.

[BOJ] C++ 12100: 2048(Easy) - 감시와 유사한 완전 탐색 구현

---

우선 연쇄가능한 점을 찾기 위해 bfs로 몇 개의 블록이 붙어있는지 판단하려 했다. 여기서 떠오른 생각이 tmp_board에 삭제를 진행하면서 4개 이상의 블록이 붙어있다면 origin_board에 그대로 복사해 주면서 자연스레 삭제처리를 하면 되고, tmp_board에 삭제를 했는데 bfs를 돌리고 보니 4개 이하의 블록이 붙어있다면 tmp_board를 origin_board 상태로 다시 돌리면 이것 또한 자연스레 삭제하지 않은 것처럼 처리되므로 하나의 함수로 연쇄를 구현할 수 있다. bfs 구현은 딱 정석대로 했는데, bfs를 잘 모른다면 아래 글을 참고하자.

[알고리즘] BFS와 DFS

bool chain(int a, int b)
{
    int cnt = 0;
    queue<pair<int, int>> q;
    visited[a][b] = true;
    q.push({a, b});

    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        tmp_board[cur.first][cur.second] = '.';
        cnt++;
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6)
                continue;
            if (origin_board[nx][ny] == '.')
                continue;
            if (visited[nx][ny] || origin_board[nx][ny] != origin_board[cur.first][cur.second])
                continue;
            q.push({nx, ny});
            visited[nx][ny] = true;
        }
    }
    return cnt >= 4;
}

 

맵을 갱신하는 부분은 각 열별로 독립적으로 갱신되므로 새로운 배열을 만들어서 cur로 새로운 배열에 삽입할 index를 기억해 두고 원래 블록을 끌어내려서 새로운 배열에 저장하는 방식으로 구현했다. 이렇게 cur을 이용하면 O(n)으로 맵을 갱신할 수 있다.

void update()
{
    // origin과 tmp 모두 아래로 끌어내릴건 끌어 내리면 됨. 새로운 배열을 만들여서 각 열별로 끌어내리기
    char res_board[12][6];
    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
            res_board[i][j] = '.';

    for (int col = 0; col < 6; col++)
    {
        int cur = 11;
        for (int i = 11; i >= 0; i--)
        {
            if (origin_board[i][col] == '.')
                continue;
            res_board[cur--][col] = origin_board[i][col];
        }
    }

    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            origin_board[i][j] = res_board[i][j];
            tmp_board[i][j] = res_board[i][j];
        }
    }
}

 

 

bfs에 자신이 있다면 바로 달라붙어서 구현할 수 있는 난이도였다.

/** 시뮬레이션 11559 Puyo Puyo **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

char origin_board[12][6];
char tmp_board[12][6];
bool visited[12][6];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int ans = 0;

bool chain(int a, int b)
{
    int cnt = 0;
    queue<pair<int, int>> q;
    visited[a][b] = true;
    q.push({a, b});

    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        tmp_board[cur.first][cur.second] = '.';
        cnt++;
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6)
                continue;
            if (origin_board[nx][ny] == '.')
                continue;
            if (visited[nx][ny] || origin_board[nx][ny] != origin_board[cur.first][cur.second])
                continue;
            q.push({nx, ny});
            visited[nx][ny] = true;
        }
    }
    return cnt >= 4;
}

void update()
{
    // origin과 tmp 모두 아래로 끌어내릴건 끌어 내리면 됨. 새로운 배열을 만들여서 각 열별로 끌어내리기
    char res_board[12][6];
    for (int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
            res_board[i][j] = '.';

    for (int col = 0; col < 6; col++)
    {
        int cur = 11;
        for (int i = 11; i >= 0; i--)
        {
            if (origin_board[i][col] == '.')
                continue;
            res_board[cur--][col] = origin_board[i][col];
        }
    }

    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            origin_board[i][j] = res_board[i][j];
            tmp_board[i][j] = res_board[i][j];
        }
    }
}

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

    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> origin_board[i][j];
            tmp_board[i][j] = origin_board[i][j];
        }
    }

    while (1)
    {
        // 연쇄 가능한 점 찾기, 찾았다면 chain함수가 true를 리턴할테고, chain 함수 내부에서 삭제 완료
        // chain함수가 false를 리턴한다면 해당 점은 연쇄 불가능하므로 다시 복구
        bool flag = false;
        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                if (origin_board[i][j] == '.')
                    continue;
                else if (chain(i, j))
                {
                    flag = true;
                    for (int i = 0; i < 12; i++)
                        for (int j = 0; j < 6; j++)
                            visited[i][j] = false;
                    for (int i = 0; i < 12; i++)
                        for (int j = 0; j < 6; j++)
                            origin_board[i][j] = tmp_board[i][j];
                    break;
                }
                else
                {
                    for (int i = 0; i < 12; i++)
                        for (int j = 0; j < 6; j++)
                            visited[i][j] = false;
                    for (int i = 0; i < 12; i++)
                        for (int j = 0; j < 6; j++)
                            tmp_board[i][j] = origin_board[i][j];
                }
            }
        }
        if (!flag)
            break;
        else
            ans++;
        // 맵 갱신
        update();
    }

    cout << ans << '\n';
}