[Algorithm] Baekjoon 11559번 : Puyo Puyo

https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

struct Node
{
    int y;
    int x;
                                                                                                                                                                                                                                                                                                       };
 
char arr[12][6];
Node nodes[12][6];
bool visited[12][6] = { false };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int answer = 0;
 
void Update() // 터진 후 빈자리에 매꾸기.
{
    for (int i = 0; i < 6; ++i)
    {
        int count = 0;
        int row = 11;
 
        while (row >= 0)
        {
            if (arr[row][i] == '.')
            {
                ++count;
            }
            else
            {
                char temp = arr[row + count][i];
                arr[row + count][i] = arr[row][i];
                arr[row][i] = temp;
            }
 
            --row;
        }
    }
}
 
bool TryBomb(int y, int x, char standard) // 4개이상이여서 터지면 true 리턴.
{
    visited[y][x] = true;
    queue<Node> q;
    q.push({ y,x });
    arr[y][x] = '.';
    int count = 1;
    vector<Node> temp;
    temp.push_back({ y,x });
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= 12) continue;
            if (nextX < 0 || nextX >= 6) continue;
            if (visited[nextY][nextX]) continue;
            if (arr[nextY][nextX] != standard) continue;
 
            ++count;
            temp.push_back({ nextY,nextX });
            visited[nextY][nextX] = true;
            arr[nextY][nextX] = '.';
            q.push({ nextY,nextX });
        }
    }
 
    if (count < 4)
    {
        for (int i = 0; i < temp.size(); ++i)
        {
            arr[temp[i].y][temp[i].x] = standard;
        }
        return false;
    }
    
    return true;
}
 
 
bool Check()
{
    int count = 0;
    memset(visited, false, sizeof(visited));
 
    for (int i = 0; i < 12; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            if (arr[i][j] != '.' && !visited[i][j])
            {
                bool check = TryBomb(i, j, arr[i][j]);
                
                if (check) ++count;
            }
        }
    }
 
    // 한번이라도 터졌으면 true 리턴. 터진게 하나도 없으면 false리턴.
    if (count >= 1) return true;
    else return false;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    for (int i = 0; i < 12; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    while (1)
    {
        if (Check()) // 터졌으면
        {
            ++answer;
            Update();
        }
        else break;
    }
 
    cout << answer;
 
    return 0;
}

어렵지않은 BFS 구현문제이다. 

arr에서 터질 조건을 갖춘(4개이상 연결된) 뿌요들을 전부 동시에 터트린 후, 만약 한덩어리라도 터진 뿌요가 있다면 빈공간에 대해 메꿔야하니 메꾸는 로직을 수행해준다. 메꾸는 로직은 그냥 각 arr의 바닥부터 제일 위까지 검사하면서, '.'이면 카운팅해주다가 뿌요를 만나면 카운팅해준 빈공간만큼 행위치로 자리를 바꿔줬다.

 

로직을 수행하다 단 하나의 뿌요덩어리가 터지지 않았다면 실행을 중단하고 연쇄값을 출력한다.