[C/C++] BOJ 11559 :: Puyo Puyo

BOJ 11559 :: Puyo Puyo

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

나의 풀이

BFS 방식으로 연결된 블록의 개수를 찾는다.

4개 이상 연결되어있으면 그 위치의 map을 모두 '.'로 변경시킨다.

모든 정점에 대한 탐색을 마치면, 한 열마다 queue로 '.'가 아닌 값을 저장한후, 가장 밑 행부터 채워넣음으로써 map을 갱신한다.

내가 실수했던 부분)

1. 원래 항상 하던 방법인 !q.empty() 로 하지 않고 다른 방식으로 하려다 보니 연결된 블록을 찾을 때 while문에서 빠져나가는 오류가 발생..

2. 문제를 제대로 안읽어서 삭제될 블록을 하나 찾을때마다 ans를 갱신함..

3. index,, 0~12미만이아니라 11~0까지로 구현하는 것에서 실수 ㅠ..

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11559/BOJ_11559.cpp

// 백준알고리즘 11559번 :: Puyo Puyo
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
 
int ans;
// 연쇄 여부
bool flag = true;
char map[12][6];
int visited[12][6];
 
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0,0,-1,1 };
 
 
// 지금 들어간 값과 같고 4개 이상 연결되어 있으면 터진다.
void bfs(int _i, int _j)
{
    queue<pair<int, int>> q;
    queue <pair<int, int>>crush;
    q.push(make_pair(_i, _j));
    crush.push(make_pair(_i, _j));
    visited[_i][_j] = 1;
    int count = 1;
    int qsz = q.size();
 
    while (qsz--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int mx = x + dx[i];
            int my = y + dy[i];
 
            if (mx < 0 || mx >= 12 || my < 0 || my >= 6) continue;
            if (visited[mx][my]) continue;
            if (map[mx][my] != map[x][y]) continue;
            visited[mx][my] = 1;
            q.push(make_pair(mx, my));
            crush.push(make_pair(mx, my));
            count++;
        }
        qsz = q.size();
    }
 
    if (count >= 4) {
        flag = true;
        // 블록 삭제 -> '.' 으로 바꾸기
        while (!crush.empty())
        {
            map[crush.front().first][crush.front().second] = '.';
            crush.pop();
        }
    }
//    cout << _i << ' ' << _j << ' ' << count << '\n';
    return;
}
int main()
{
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> map[i][j];
        }
    }
 
    while (1)
    {
        flag = false;
        memset(visited, 0, sizeof(visited));
        for (int i = 11; i >= 0; i--)
        {
            for (int j = 0; j < 6; j++)
            {
                if (map[i][j] != '.' && visited[i][j] != 1)
                {
                    bfs(i, j);
                }
            }
        }
        if (!flag) break;
        ans++;
 
        // 블록 밑으로 내리기
        queue<char> qu;
        for (int i = 0; i < 6; i++)
        {
            for (int j = 11; j >= 0; j--)
            {
                if (map[j][i] != '.')
                {
                    qu.push(map[j][i]);
                    map[j][i] = '.';
                }
            }
            int standard = 11;
            while (!qu.empty())
            {
                map[standard][i] = qu.front();
                qu.pop();
                standard--;
            }            
        }
    }
 
    cout << ans;
 
    return 0;
}