백준 11559번 Puyo Puyo

🔒[문제 url]

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

🔑알고리즘

입력 조건에서 뿌요는 전부 아래로 떨어진 상태임을 명시했으므로, 구현 순서는 다음과 같다.

1. 모든 뿌요에 대해 BFS를 통해 연결된 같은 색 뿌요의 갯수를 파악한다.
2. 같은 색의 뿌요가 4개 이상 연결되어있다면, 터뜨린다.
3. 모든 BFS를 마쳤을 때, 터진 뿌요가 있다면 연쇄 횟수를 1 추가한다.
4. 터진 뿌요가 있다면, 나머지 뿌요를 아래로 떨어트린다.
5. 1 ~ 4를 터질 뿌요가 없을 때까지 반복한 후, 연쇄 횟수를 출력한다.

• 떨어지는 뿌요를 어떻게 구현하는가?
  • 12번째 행의 뿌요는 더이상 떨어질 곳이 없으므로, 11번째 행의 원소부터 위로 올라가며 차례대로 떨어트린다.
  • 뿌요의 아랫 행이 범위를 벗어나거나 빈 칸이 아니라면 계속 떨어트린다.

🐾부분 코드

bool BFS(int x,int y)
{
    // size가 4 이상이면 폭발
    vector<pair<int,int>> bomb;

    queue<pair<int,int>> q;
    bomb.push_back({x,y});
    q.push({x,y});
    visited[x][y] = true;

    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < 12 && 0 <= ny && ny < 6)
            {//Check range
                if(!visited[nx][ny] && map[nx][ny] == map[x][y])
                {//아직 방문하지 않았고 같은 색의 Puyo라면
                    bomb.push_back({nx,ny});
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    //연결된 같은 색의 Puyo가 4개 이상이면 폭발
    if(bomb.size() >= 4)
    {
        for(int i = 0; i < bomb.size(); i++)
            map[bomb[i].first][bomb[i].second] = '.';
        return true;
    }
    return false;
}

<BFS 및 뿌요 연쇄 함수>
뿌요가 속한 모든 지점를 기준으로 BFS를 진행한다.
bomb에 연결된 모든 같은 색의 뿌요의 지점을 push한 후,
bomb.size()가 4 이상이라면 모두 빈 칸으로 바꾼다.
뿌요가 터진다면 true를, 터지지 않는다면 false를 반환한다.

void movePuyo()
{//Puyo 아래로 내리기
    for(int j = 0; j < 6; j++)
        for(int i = 10; i >= 0; i--)//아래의 puyo부터 옮김
            if(map[i][j] != '.')
            {
                int idx = i;//현재 이동중인 puyo의 row index

                while(idx + 1 < 12 && map[idx + 1][j] == '.')
                {//아랫행이 범위를 벗어나지 않으며 puyo가 없다면 계속 내린다
                    map[idx + 1][j] = map[idx][j];
                    map[idx][j] = '.';
                    idx++;
                }
            }
}

<뿌요 내리는 함수>
아랫행부터 위로 올라가며 뿌요를 떨어트린다.
idx 변수에 떨어질 뿌요의 row index를 할당하여 더이상 떨어지지 못할때까지 떨어트린다.

void SOLVE()
{
    int ans = 0;

    while(true)
    {
        // 연쇄
        bool erased = false;
        for(int i = 0; i < 12; i++)
            for(int j = 0; j < 6; j++)
            {
                if(map[i][j] != '.')
                {
                    if(BFS(i,j)) erased = true;
                    memset(visited,false,sizeof visited);
                }
            }

        // 터진 뿌요가 있다면 1연쇄 추가
        if(erased) ans++;
        else break;

        // 아래로 떨어짐
        if(erased) movePuyo();
    }

    cout << ans;
}

<1 ~ 4번 반복 및 답 출력>
erased 변수를 선언하여 BFS() 함수로부터 반환받은 bool 값을 저장한다. 즉, 터진 뿌요가 있다면 true가 할당되어 연쇄 횟수가 1 늘어나고 뿌요를 아래로 내린다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

char map[13][7];
bool visited[13][7];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};;

void INPUT()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i = 0; i < 12; i++)
        for(int j = 0; j < 6; j++)
            scanf("%1s",&map[i][j]);
}


bool BFS(int x,int y)
{
    // size가 4 이상이면 폭발
    vector<pair<int,int>> bomb;

    queue<pair<int,int>> q;
    bomb.push_back({x,y});
    q.push({x,y});
    visited[x][y] = true;

    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(0 <= nx && nx < 12 && 0 <= ny && ny < 6)
            {//Check range
                if(!visited[nx][ny] && map[nx][ny] == map[x][y])
                {//아직 방문하지 않았고 같은 색의 Puyo라면
                    bomb.push_back({nx,ny});
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    //연결된 같은 색의 Puyo가 4개 이상이면 폭발
    if(bomb.size() >= 4)
    {
        for(int i = 0; i < bomb.size(); i++)
            map[bomb[i].first][bomb[i].second] = '.';
        return true;
    }
    return false;
}

void movePuyo()
{//Puyo 아래로 내리기
    for(int j = 0; j < 6; j++)
        for(int i = 10; i >= 0; i--)//아래의 puyo부터 옮김
            if(map[i][j] != '.')
            {
                int idx = i;//현재 이동중인 puyo의 row index

                while(idx + 1 < 12 && map[idx + 1][j] == '.')
                {//아랫행이 범위를 벗어나지 않으며 puyo가 없다면 계속 내린다
                    map[idx + 1][j] = map[idx][j];
                    map[idx][j] = '.';
                    idx++;
                }
            }
}

void SOLVE()
{
    int ans = 0;

    while(true)
    {
        // 연쇄
        bool erased = false;
        for(int i = 0; i < 12; i++)
            for(int j = 0; j < 6; j++)
            {
                if(map[i][j] != '.')
                {
                    if(BFS(i,j)) erased = true;
                    memset(visited,false,sizeof visited);
                }
            }

        // 터진 뿌요가 있다면 1연쇄 추가
        if(erased) ans++;
        else break;

        // 아래로 떨어짐
        if(erased) movePuyo();
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

2048(Easy)를 통해 단련된 탓에 movePuyo()를 쉽게 구현할 수 있어 그냥 일반적인 BFS 문제라고 느껴졌다. Gold 하위구간 시뮬레이션 문제는 막힘없이 풀 수 있는만큼은 성장한 것같다!