백준 16768번 Mooyo Mooyo

🔒[문제 url]

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

🔑알고리즘

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

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

• 떨어지는 무요를 어떻게 구현하는가?
  • 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 < n && 0 <= ny && ny < 10)
            {//Check range
                if(!visited[nx][ny] && map[nx][ny] == map[x][y])
                {//아직 방문하지 않았고 같은 색의 Mooyo라면
                    bomb.push_back({nx,ny});
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    //연결된 같은 색의 Mooyo가 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 moveMooyo()
{//Mooyo 아래로 내리기
    for(int j = 0; j < 10; j++)
    {
        for(int i = n-2; i >= 0; i--)
        {
            if(map[i][j] != 0)
            {
                int idx = i;

                while(idx + 1 < n && map[idx + 1][j] == 0)
                {
                    map[idx + 1][j] = map[idx][j];
                    map[idx][j] = 0;
                    idx++;
                }
            }
        }
    }
}

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

void SOLVE()
{
    int ans = 0;

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

        // 터진 무요가 있다면 1연쇄 추가
        if(!erased) 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;

int n,k;
int map[101][11];
bool visited[101][11];
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);
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 10; j++)
            scanf("%1d",&map[i][j]);
}


bool BFS(int x,int y)
{
    // size가 k 이상이면 폭발
    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())
    {
        int x = q.front().first;
        int 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 < n && 0 <= ny && ny < 10)
            {
                if(!visited[nx][ny] && map[nx][ny] == map[x][y])
                {
                    bomb.push_back({nx,ny});
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }

    if(bomb.size() >= k)
    {
        for(int i = 0; i < bomb.size(); i++)
        {
            map[bomb[i].first][bomb[i].second] = 0;
        }
        return true;
    }
    return false;
}

void moveMooyo()
{
    for(int j = 0; j < 10; j++)
    {
        for(int i = n-2; i >= 0; i--)
        {
            if(map[i][j] != 0)
            {
                int idx = i;

                while(idx + 1 < n && map[idx + 1][j] == 0)
                {
                    map[idx + 1][j] = map[idx][j];
                    map[idx][j] = 0;
                    idx++;
                }
            }
        }
    }

}

void SOLVE()
{

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

        // 터진 무요가 없다면 끝
        if(!erased) break;

        // 아래로 떨어짐
        moveMooyo();
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 10; j++)
            cout << map[i][j];
        cout << '\n';
    }
}

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

🥇문제 후기

Puyo Puyo와 짝궁 문제!(rating 개꿀..)