[백준 11559] - Puyo Puyo(C++)[골드4]

📕문제

---

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1 연쇄가 시작된다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1 연쇄씩 늘어난다.

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한 번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

📕입력

---

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.

이때. 은 빈 공간이고. 이 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈칸이 있는 경우는 없다.

📕출력

---

현재 주어진 상황에서 몇 연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.

👀문제 해석

문제를 읽어보면 중요한 포인트가 3개 정도 있다.

1. 우선 연결 여부는 상하좌우 4방향으로만 인정한다.
   1. 여기서 상하좌우로 쭉쭉 이동해서 같은색 뿌요들이 4개 이상이라면 그 뿌요들은 없어진다.
2. 뿌요들이 없어지면 위에 있는 뿌요들은 중력의 영향을 받아서 아래로 떨어진다.
3. 동시에 연쇄가 터지더라도 같은 시간대에 일어나면 연쇄는 한번이라고 처리한다.

이러한 3가지 쟁점을 두고 문제에 접근하면 문제 풀기가 용이할 것입니다.

 

🔎문제 풀이

1️⃣변수선언

• result는 연쇄 횟수, step과 alph는 bfs를 하는 데 사용되는 변수, flag는 연쇄발생에 대한 여부를 저장
• q는 bfs를 할 때 사용되는 q이고, 2차원 배열에 대한 좌표가 들어감.
• graph는 입력받는 행렬, visit는 방문처리에 대한 배열
• x, y는 방향벡터이고, color는 뿌요의 색깔을 저장하고, p는 연쇄 성공한 2차원 배열 좌표가 들어감.

2️⃣알고리즘

• 반복문을 돌다가 검사를 진행
  • 해당 검사는 빈 공간이 아니고, 방문하지 않았어야 함.
  • 검사에 통과하면 해당 좌표를 q에 넣고, bfs를 진행
• bfs
  • 다른 bfs와 같이 큐가 완전히 빌 때까지 진행한다.
  • 좌표와 알파벳을 뽑아주고, pop을 한다.
    • 만약 해당 좌표가 이미 방문한 좌표라면 continue 실행
    • 아니라면 해당 색깔에 대한 count를 증가시켜 주고, 방문 처리를 해준다.
  • 상하좌우로 탐색
    • 좌표가 적절하지 않은 좌표라면 continue 실행
      • 적절하지 않은 좌표 -> 배열을 넘어가거나, 큐에서 뽑은 알파벳과 다른 경우, 방문한 경우
    • 적절한 좌표라면 큐에 넣어줌.
• 탐색이 끝난 뒤
  • 같은 색깔의 뿌요가 4개 이상이라면 연쇄성공,
    flag [연쇄여부] = true로 바꿔주고, color를 다시 0으로 초기화해 줌.
  • 같은 색깔의 뿌요가 4개 이하라면 연쇄실패,
    p에는 쓰레기 좌표가 들어갔으므로, 특정 뿌요 색깔 수만큼 p를 지워줌.
• bfs함수가 완전히 끝난 뒤
  • 방문배열을 초기화시켜 줌.
  • p에는 연쇄성공한 좌표가 들어있고, 해당 좌표를 빈 공간으로 초기화
• 중력적용
  • 빈 공간이 아니라면 큐에 해당 알파벳을 넣은 뒤, 큐가 빌 때까지 알파벳을 넣어준다.
  • 만약 큐가 비면 전부 다 처리 해줌.
• 연쇄 여부
  • flag값이 true라면 연쇄 횟수를
  • flag값이 false라면 연쇄가 더 이상 연쇄가 불가능하므로 종료해 줌.

💻코드

주석이 이해 안 가시면 음,,, 댓글 부탁@

/*
백준 골드4 뿌요뿌요
*/

/*
같은 색 뿌요가 상하좌우로 연결되어 있으면 한꺼번에 없어짐. -> 1연쇄
뿌요들은 계속 아래로 떨어짐.
동 시간 대에 터지면 1연쇄라고 처리하는 거 같음.
RGBPY 6개의 색깔 .은 빈공간
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int result = 0;
int step;
char alph;
bool flag = false;
queue<pair<int, int>> q;
vector<vector<char>> graph;
vector<vector<int>> visit;
vector<int> x = {1, -1, 0, 0};
vector<int> y = {0, 0, 1, -1}; 
vector<int> color = {0, 0, 0, 0, 0};
vector<pair<int, int>> p;
void PuPu();
int select_color(int x, int y);
void print_ary();
int main()
{
    graph.resize(12, vector<char>(6, 0));
    visit.resize(12, vector<int>(6, 0));
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> graph[i][j];
        }
    }
    while (1)
    {
        flag = false;
        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                if (graph[i][j] != '.' && visit[i][j] == 0) //빈공간이 아니고, 아직 방문 안한 좌표
                {
                    q.push(make_pair(i, j));
                    PuPu();
                }
            }
        }
        visit.assign(12, vector<int>(6, 0));  //행렬을 한번 쫙 검사하면 방문처리를 다시 초기화
        for (int k = 0; k < p.size(); k++) //p에는 4개이상의 같은 문자열된 블록의 좌표가 들어있음.
        {
            int ax = p[k].first;
            int ay = p[k].second;
            graph[ax][ay] = '.'; //뿌요를 터트렸다면 해당 좌표를 빈공간으로 만들어줌.
        }
        p.clear(); //p 초기화
        for (int i = 0; i < 6; i++) { //중력적용하기, 내릴 수 있는 끝까지 블록을 내리기.
            queue<char> queue;
            for (int j = 11; j >= 0; j--)
                if (graph[j][i] != '.') queue.push(graph[j][i]);
            for (int j = 11; j >= 0; j--) {
                if (queue.empty()) {
                    graph[j][i] = '.';
                    continue;
                }
                graph[j][i] = queue.front();
                queue.pop();
            }
        }
        if (flag == true) //만약 한번이라도 연쇄가 일어났다면 연쇄 횟수를 늘려야한다.
        {
            result++;
        }
        if (flag == false) //연쇄가 없었다면, 더이상 연쇄할수 없다는 뜻이기에 종료
            break;
    }
    cout << result;
}
int select_color(int x, int y) //색깔에 대한 주소를 지정해줌.
{
    switch (graph[x][y])
    {
    case 'R':
        return 0;
    case 'G':
        return 1;
        break;
    case 'B':
        return 2;
    case 'P':
        return 3;
    case 'Y':
        return 4;
    }
}
void PuPu()
{
    while (!q.empty())
    {
        int mx = q.front().first;
        int my = q.front().second;
        alph = graph[mx][my];
        step = select_color(mx, my);
        q.pop();
        if (visit[mx][my] == 1)
        {
            continue;
        }
        color[step]++; //해당 컬러에 대한 블록 수를 증가시켜줌.
        p.push_back(make_pair(mx, my)); //p에 좌표를 저장해줌. -> 나중에 빈공간으로 교체해주기 위해서
        visit[mx][my] = 1; //방문처리 
        for (int i = 0; i < 4; i++)
        {
            int fx = mx + x[i];
            int fy = my + y[i];
            if (fx < 0 || fx >= 12 || fy < 0 || fy >= 12 || graph[fx][fy] != alph || visit[fx][fy] == 1) // 부적절한 좌표
            {
                continue;
            }
            q.push(make_pair(fx, fy));
        }
    }
    if (color[step] < 4) //만약 4개 이상의 블록을 연결못했다면 실패한것임.
    {
        for (int i = 0; i < color[step]; i++) //해당 블록 수만큼 다시 좌표를 뺴줌.
        {
            p.pop_back();
        }
        color[step] = 0; //0으로 초기화
    }
    if (color[step] >= 4) //만약 4개 이상의 블록을 연결했다면 성공
    {
        flag = true;
        color[step] = 0;
    }
}
void print_ary()
{
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

 

✔느낀 점

• 구현 문제는 정말 알고리즘 선택이 중요한 것 같습니다... 반복된 훈련으로 문제가 요구하는 탁월한 자료구조와 알고리즘을 선택하는 것이 필요하다고 느꼈습니다.
• 중력 적용에 대한 코드 짜기가 굉장히 애먹었습니다.
• select_color 같은 함수를 안 짜고 깔끔하게 짤 수 있었을 거 같은데 너무 복잡하게 짠 것 같아서 부끄럽네요,,