[BOJ 11559] Puyo Puyo (C++)

Puyo Puyo (Gold 5)

문제

전체 문제 보기

11559번: Puyo Puyo

접근법

이번 문제는 BFS를 활용한 구현 문제입니다. BFS를 활용해서 현재 맵에 있는 뿌요를 탐색하여 4개 이상 모여있는 뿌요들은 모두 터트려주고, 빈 공간을 채워서 뿌요를 내리는 동작을 반복하여 문제를 해결할 수 있습니다. 전체 노드의 개수는 6 * 12로 작기 때문에 완전 탐색으로 계산하더라도 충분히 시간 내에 계산 가능합니다.

구현

메인 반복문

먼저 메인 반복문 로직은 다음과 같습니다. 메인 반복문은 아래의 기능을 합니다.

• 현재 맵에서 터트릴 수 있는 모든 뿌요를 터트린다.
  • 터진 뿌요가 있다면 터진 뿌요 위의 뿌요들을 끌어 내리고, answer를 1 증가시킨다.
  • 터진 뿌요가 없다면 탐색을 종료한다.

int main()
{    
    // 데이터 입력 부분 생략

    int answer{};
    while (Combo(field))
    {
        PullDown(field);
        answer++;
    }
    std::cout << answer;
    return 0;
}

Combo 함수

Combo 함수에서는 맵의 모든 노드를 탐색하며 BFS를 활용하여 터트릴 수 있는 뿌요를 탐색합니다. 한번 이상 뿌요를 터트렸다면 true를 반환합니다. BFS는 (i, j) 위치의 뿌요를 탐색하여 동일한 뿌요가 4개 이상 인접했는지 확인하고, 4개 이상이라면 뿌요를 터트린 후 true를 반환합니다. (BFS 함수는 아래의 전체 코드를 참고해주세요.)

bool Combo(Field& field)
{
    //PrintField(field);
    bool result{};
    Visited visited{};
    for(int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
        {
            if (BFS(field, visited, i, j))
                result = true;
        }
    return result;
}

전체 소스 코드

다음과 같이 코드를 작성하였습니다.

#include <iostream>
#include <algorithm>
#include <array>
#include <string>
#include <queue>
#define endl '\n'

constexpr char R{ 'R' }, G{ 'G' }, B{ 'B' }, P{ 'P' }, Y{ 'Y' }, E{ '.' };
constexpr std::array<int, 4> dr = { 1,-1,0,0 };
constexpr std::array<int, 4> dc = { 0,0,1,-1 };
using Field = std::array<std::string, 12>;
using Visited = std::array<std::array<bool, 6>, 12>;
struct Pos {
    Pos() = default;
    Pos(int r, int c) : row(r), col(c) {}
    int row{};
    int col{};
};
struct Move {
    Move() = default;
    Move(int r, int c, int d) : pos(r, c), dep(d) {}
    Pos pos;
    int dep{};
};
void PrintField(const Field& field)
{
    for (std::string row : field)
    {
        std::cout << row << endl;
    }
    std::cout << endl;

}
bool IsValid(const Move& next)
{
    if (next.pos.col < 0 || next.pos.col >= 6 || next.pos.row < 0 || next.pos.row >= 12)
        return false;
    return true;
}
bool BFS(Field& field, Visited& visited, int row, int col)
{
    if (field[row][col] == E) return false;
    if (visited[row][col] == true) return false;
    // 현재 문자
    char tar = field[row][col];
    std::queue<Move> q;
    std::vector<Pos> puyo;
    puyo.reserve(72);

    q.push(Move(row, col, 0));
    puyo.emplace_back(row, col);
    field[row][col] = E;
    while (!q.empty())
    {
        Move cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            Move next(cur.pos.row + dr[i], cur.pos.col + dc[i], cur.dep + 1);
            if (IsValid(next) == false) continue;
            if (field[next.pos.row][next.pos.col] == tar)
            {
                field[next.pos.row][next.pos.col] = E;
                q.push(next);
                puyo.emplace_back(next.pos.row, next.pos.col);
            }
        }
    }
    if (puyo.size() >= 4)
    {
        return true;
    }
    else
    {
        for (const Pos& pos : puyo)
        {
            field[pos.row][pos.col] = tar;
            visited[pos.row][pos.col] = true;
        }
        return false;
    }
}

bool Combo(Field& field)
{
    //PrintField(field);
    bool result{};
    Visited visited{};
    for(int i = 0; i < 12; i++)
        for (int j = 0; j < 6; j++)
        {
            if (BFS(field, visited, i, j))
                result = true;
        }
    return result;
}
void PullDown(Field& field)
{
    for (int i = 11; i >= 0; --i)
    {
        for (int j = 0; j < 6; ++j)
        {
            if (field[i][j] == E)
            {
                int idx = i;
                while (idx > 0 && field[idx][j] == E)
                {
                    idx--;
                }
                field[i][j] = field[idx][j];
                field[idx][j] = E;
            }
        }
    }
}
int main()
{    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    Field field;
    for (std::string& row : field)
    {
        std::cin >> row;
    }

    int answer{};
    while (Combo(field))
    {
        PullDown(field);
        answer++;
    }
    std::cout << answer;
    return 0;
}