백준 11559번 Puyo Puyo

문제 링크입니다: https://www.acmicpc.net/problem/11559

BFS(Breadth First Search) 알고리즘을 응용하여 푸는 시뮬레이션 문제였습니다.

알고리즘은 아래와 같습니다.

1. 필드를 밑에서부터 위로 하나하나 확인하면서 BFS 알고리즘을 적용하여 4개 이상의 같은 색깔 블록이 상하좌우로 연결되었는지 확인합니다

i) 4개 이상의 같은 색깔이 연속되어 붙어있으면 터뜨려야하므로 벡터에 넣습니다.

ii) 동시에 터뜨릴 수 있다면 하나의 연쇄라고 생각하기 때문에 모든 색깔의 블럭에 대해 고려해줘야합니다.

2. 블록을 터뜨렸다면 블록들의 위치가 바뀌기 때문에 while문을 통해 다시 1번을 진행하고 만약 또 터뜨릴 수 있다면 연쇄를 추가해줍니다.

3. 터뜨릴 수 있는 모든 블럭을 터뜨렸다면 최대 연쇄를 출력해줍니다.

#include <iostream>

#include <string>

#include <queue>

#include <algorithm>

using namespace std;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int result;

string Puyo[12];

 

//정렬할 때 필요한 cmp 함수

bool cmp(pair<int, int> a, pair<int, int> b)

{

        if (a.second < b.second)

                 return true;

        else if (a.second == b.second)

        {

                 if (a.first < b.first)

                         return true;

                 return false;

        }

        return false;

}

 

int BFS(void)

{

        queue<pair<int, int>> q;

        int cnt = 0;

 

        while (1)

        {

                 vector<pair<int, int>> v; //부실 블럭 저장

                 bool visited[12][6] = { false };

                 for (int y = 11; y >= 0; y--)

                 {

                         for (int x = 0; x < 6; x++)

                         {

                                 if (Puyo[y][x] == '.')

                                          continue;

                                 else

                                 {

                                          queue<pair<int, int>> popped;

                                          char color = Puyo[y][x];

                                          q.push({ y, x });

                                          visited[y][x] = true;

 

                                          while (!q.empty())

                                          {

                                                  int curY = q.front().first;

                                                  int curX = q.front().second;

                                                  popped.push({ curY, curX });

                                                  q.pop();

 

                                                  for (int i = 0; i < 4; i++)

                                                  {

                                                          int nextY = curY + moveDir[i].y;

                                                          int nextX = curX + moveDir[i].x;

 

                                                          if (0 <= nextY && nextY < 12 && 0 <= nextX && nextX < 6)

                                                                   if (!visited[nextY][nextX] && Puyo[nextY][nextX] == color)

                                                                   {

                                                                           visited[nextY][nextX] = true;

                                                                           q.push({ nextY, nextX });

                                                                   }

                                                  }

                                          }

 

                                          if (popped.size() >= 4) //같은 색깔인 블록이 4개 이상이면 벡터에 넣는다

                                          {

                                                  while (!popped.empty())

                                                  {

                                                          v.push_back({ popped.front().first, popped.front().second });

                                                          popped.pop();

                                                  }

                                          }

                                 }

                         }

                 }

                 //부실 블럭이 있으면 부시고 블록을 내린다

                 if (v.size() > 0)

                 {

//x를 기준으로 오름차순 정렬

                         sort(v.begin(), v.end(), cmp);

                         for (int i = 0; i < v.size(); i++)

                         {

                                 for (int j = v[i].first; j > 0; j--)

                                          Puyo[j][v[i].second] = Puyo[j - 1][v[i].second];

                                 Puyo[0][v[i].second] = '.';

                         }

                         cnt++; //연쇄 추가

                 }

                 else

                         break;

        }

        return cnt;

}

 

int main(void)

{

        for (int y = 0; y < 12; y++)

                 cin >> Puyo[y];

 

        cout << BFS() << "\n";

        return 0;

}

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~