😄 알고리즘 문제를 풀기만 하는 것이 아닌 어떻게 풀었는지에 대해서 정리하면 좋을 것 같아서 만드는 글입니다.

💻 백준 11559 문제

문제

입력

문제는 대충 테트리스라고 생각하면 편하다.
테트리스지만, 이미 쌓아올리는 과정의 테트리스가 아닌 이미 쌓아올려진 테트리스.
상하좌우로 4개의 같은 블록이 연결되어있으면 터뜨리고 위의 블록을 내리는 작업이 필요하다.
나는 밑의 글에서 해당 알고리즘으로 풀어야겠다고 생각했다.

• 상하좌우로 4개의 블록이 연결되어있다면 ? -> BFS 알고리즘
• 위의 블록을 밑으로 내리는 과정 -> 시뮬레이션, 구현 알고리즘

4개 이상의 블록

💻 BFS
void bfs(int y, int x)
{
    int cnt = 1;
    queue<pair<int, int> > q;
    vector<pair<int, int> > v;
    q.push(make_pair(y, x));
    v.push_back(make_pair(y, x));
    check[y][x] = 1;
    while(!q.empty())
    {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= 12 || nx >= 6 || ny < 0 || nx < 0 || check[ny][nx])
                continue;
            if(field[y][x]==field[ny][nx])
            {
                q.push(make_pair(ny, nx));
                v.push_back(make_pair(ny, nx));
                check[ny][nx] = 1;
                cnt++;
            }
        }
    }
    if (cnt >= 4)
    {
        for (auto i : v)
        {
            field[i.first][i.second] = '.';
        }
        tag = true;
    }
}

• 기존의 좌표(2차원)BFS에서 vector를 넣어줬습니다.
• vector는 상하좌우를 통한 연결된 블록의 수가 4개 이상일 때 해당 블록을 .로 바꿔주는 역할을 담당합니다.
• 같은 블록인 경우에 있어서 if(field[y][x]==field[ny][nx]) queue에 좌표를 넣어줬습니다.

while

4개 이상의 연결되어있는 블록이 나오는 경우까지 계속! 계속! 돌려줍니다.

빈 자리에 블록을 내려주는 작업.

💻 구현, 시뮬레이션

for (int i = 11; i >= 1; i--)
        {
            for (int j = 0; j < 6; j++)
            {
                if(field[i][j]=='.')
                {
                    for (int k = i - 1; k >= 0; k--)
                    {
                        if(field[k][j]!='.')
                        {
                            field[i][j] = field[k][j];
                            field[k][j] = '.';
                            break;
                        }
                    }
                }
            }
        }

• 맵을 모두 돌려줍니다.
• . 인 경우에 위를 탐색하며 . 가 아닌 블록을 끌어 내려주는 작업입니다.
• 복잡한 구현이지만 제가 생각해낸 최선이었던 것 같습니다.. ㅠ

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>

using namespace std;

#define endl "\n"

bool tag = true;
char field[12][6];
bool check[12][6];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

void bfs(int y, int x)
{
    int cnt = 1;
    queue<pair<int, int> > q;
    vector<pair<int, int> > v;
    q.push(make_pair(y, x));
    v.push_back(make_pair(y, x));
    check[y][x] = 1;
    while(!q.empty())
    {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= 12 || nx >= 6 || ny < 0 || nx < 0 || check[ny][nx])
                continue;
            if(field[y][x]==field[ny][nx])
            {
                q.push(make_pair(ny, nx));
                v.push_back(make_pair(ny, nx));
                check[ny][nx] = 1;
                cnt++;
            }
        }
    }
    if (cnt >= 4)
    {
        for (auto i : v)
        {
            field[i.first][i.second] = '.';
        }
        tag = true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 0; i < 12; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < 6; j++)
        {
            field[i][j] = s[j];
        }
    }
    int result = 0;
    while (tag)
    {
        tag = false;
        memset(check, 0, sizeof(check));
        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                if (field[i][j] != '.' && !check[i][j])
                {
                    bfs(i, j);
                }
            }
        }
        if (tag == false)
            break;
        result++;
        for (int i = 11; i >= 1; i--)
        {
            for (int j = 0; j < 6; j++)
            {
                if(field[i][j]=='.')
                {
                    for (int k = i - 1; k >= 0; k--)
                    {
                        if(field[k][j]!='.')
                        {
                            field[i][j] = field[k][j];
                            field[k][j] = '.';
                            break;
                        }
                    }
                }
            }
        }
    }
    cout << result << endl;
}