백준 11559 Puyo Puyo(dfs)

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

11559번: Puyo Puyo

#include <iostream>
#include <vector>

using namespace std;

typedef struct
{
    int x, y;
} Dir;

Dir dirMove[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool visited[12][6];
string graph[12];
int cnt;
int result;
bool chk;
int puyopuyo;
int breakChk;
vector<pair<int, int>> p;
void dfs(int x, int y)
{
    p.push_back(make_pair(x, y));
    visited[x][y] = true;
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + dirMove[i].x;
        int nextY = y + dirMove[i].y;
        if (0 <= nextX && nextX < 12 && 0 <= nextY && nextY < 6)
        {
            if (!visited[nextX][nextY] && graph[x][y] == graph[nextX][nextY])
            {
                cnt++;
                dfs(nextX, nextY);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 0; i < 12; i++)
        cin >> graph[i];
    while (1)
    {
        // 같은게 4개 이상 붙어있다면 터트려서 .으로 만든다
        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                if (!visited[i][j] && graph[i][j] != '.')
                {
                    dfs(i, j);
                    if (cnt >= 3)
                    {
                        breakChk++;
                        for (int k = 0; k < p.size(); k++)
                        {
                            graph[p[k].first][p[k].second] = '.';
                        }
                    }
                    p.clear();
                    cnt = 0;
                }
            }
        }
        if (breakChk == 0)
            break;
        //터트릴건 다 터트렸으니 터진 빈칸들을 위에 있는 것들로 채운다
        while (1)
        {

            for (int i = 11; i >= 1; i--)
            {
                for (int j = 0; j < 6; j++)
                {
                    if (graph[i][j] == '.' && graph[i - 1][j] != '.')
                    {
                        char tmp = graph[i][j];
                        graph[i][j] = graph[i - 1][j];
                        graph[i - 1][j] = tmp;
                    }
                }
            }
            chk = false;
            for (int i = 11; i >= 1; i--)
            {
                for (int j = 0; j < 6; j++)
                {
                    if (graph[i][j] == '.' && graph[i - 1][j] != '.')
                        chk = true;
                }
            }
            if (!chk)
                break;
        }

        for (int i = 0; i < 12; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                visited[i][j] = false;
            }
        }
        breakChk = 0;
        puyopuyo++;
    }
    cout << puyopuyo;
    // for (int i = 0; i < 12; i++)
    // {
    //     for (int j = 0; j < 6; j++)
    //     {
    //         cout << graph[i][j];
    //     }
    //     cout << "\n";
    // }
}

아 엄청 오래걸렸다............

 

이래저래 실수들을 많이 하는 바람에 오래 걸렸다.

 

문제에 제시된

 

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

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

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

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

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

를 while loop 속에 순서대로 넣었다고 생각하면 이해하기 쉽다. dfs문제이긴 했지만 dfs로 푸는 것은 어렵지 않았지만 이 설명을 코드로 구현하는 것이 개인적으로 조금 까다로웠다.