11559

11559번 - Puyo Puyo

시뮬레이션 문제.

dfs를 돌면서, 길이가 4이상인 값들은 맵에서 전부 '.' 로 바꿔준다.

era 라는 함수를 써서 dfs와 똑같이 돌면서 값을 . 으로 바꿔주는 함수를 이용했다.

dfs를 이용해서는 return 을 이용해서 길이 체크하는 코딩이 생각이 나지 않아서, 값이 작아서 두번 이용했다.

그리고 다시 전체를 돌면서 이동시켜준다.

이때는 맨 밑 바닥부터 시작해서 위에 값들과 swap 시켜주는 방식으로 문제를 풀었다.

<정답 코드>

#include<iostream>
 
using namespace std;
 
int cnt, len;
char map[12][6];
bool chk[12][6];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
void init()
{
    cnt = 0;
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            chk[i][j] = false;
        }
    }
}
void dfs(int x, int y,char c)
{
    len++;
    chk[x][y] = true;
 
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 0 && ny >= 0 && nx < 12 && ny < 6 && !chk[nx][ny] && map[nx][ny]==c)
        {
            dfs(nx, ny,c);
        }
    }
}
 
void era(int x, int y, char c)
{
    map[x][y] = '.';
 
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx >= 0 && ny >= 0 && nx < 12 && ny < 6 && map[nx][ny] == c)
        {
            era(nx, ny, c);
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> map[i][j];
        }
    }
 
    int combo = 0;
 
    while (true)
    {
        init();
        // 지우기
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] != '.' && !chk[i][j])
                {
                    len = 0;
                    dfs(i, j, map[i][j]);
                    if (len>=4)
                    {
                        cnt++;
                        era(i, j, map[i][j]);
                    }
                }
            }
        }
        
        //아래로 이동 시키기
        for (int j = 0; j < 6; j++)
        {
            for (int i = 11; i >= 0; i--)
            {
                if (map[i][j] == '.')
                {
                    for (int u = i - 1; u >= 0; u--)
                    {
                        if (map[u][j] != '.')
                        {
                            char tmp = map[i][j];
                            map[i][j] = map[u][j];
                            map[u][j] = tmp;
                            break;
                        }
                    }
                }
            }
        }
 
        if (cnt == 0)
        {
            break;
        }
        else
        {
            combo++;
        }
    }
 
    cout << combo << "\n";
 
 
    return 0;
}