11559번 Puyo Puyo

최신 풀이 : https://hsdevelopment.tistory.com/330

2015년 연세대학교 프로그래밍 경시대회 문제이다.

보자마자 DFS를 떠올렸다. 후에 BFS로 다시 풀어봐야겠다.

이 문제 역시 거의 풀었다고 생각했는데, 안 풀려서 다른 블로거 분 코드를 참고하였다.

이 문제를 통해 깨달은 것

1. 112번 째 코드와 같이 변수가 '음수'가 될 수 있음을 기억해두자. 이것 때문에 몇 시간 동안 다른 분 코드와 같이 비교하면서 생각을 했다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
char map[13][7];
 
bool visit[13][7] = { false, };
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int cnt = 0;
 
void DFS(int r, int c, char color)
{
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (0 <= y && y < 12 && 0 <= x && x < 6 && !visit[y][x] && map[y][x] == color)
        {
            ++cnt;
 
            DFS(y, x, color);
        }
    }
}
 
void cleanMap(int r, int c, char color)
{
    map[r][c] = '.'; // 갱신
 
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (0 <= y && y < 12 && 0 <= x && x < 6 && map[y][x] == color)
        {
            cleanMap(y, x, color);
        }
    }
}
 
int main(void)
{
    int ans = 0;
 
    for (int i = 0; i < 12; i++)
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> map[i][j];
        }
    }
 
    while (1)
    {
        int changeBreak = 0;
 
        memset(visit, false, sizeof(visit)); // 초기화
 
        for (int i = 0; i < 12; i++)
        {        
            for (int j = 0; j < 6; j++)
            {
                cnt = 0; // 다시 다른 뿌요가 4개 같이 있을 수 있으니, 0으로 다시 초기화.
 
                if (!visit[i][j] && map[i][j] != '.')
                {
                    ++cnt;
 
                    DFS(i, j, map[i][j]);
 
                    if (cnt >= 4) // 뿌요 4개 이상이 같이 있다면
                    {
                        ++changeBreak; // 변화가 있으면 증가
 
                        cleanMap(i, j, map[i][j]); // 맵 바꿔주기
                    }
                }
            }
        }
 
        // 블록 내리기 
        for (int column = 0; column < 6; column++)
        {
            for (int row = 11; row >= 0; row--)
            {
                if (map[row][column] == '.')
                {
                    int replace_row = row - 1;
 
                    while (replace_row >= 0 && map[replace_row][column] == '.')
                    {
                        // 행 값은 0 이상이고 '.' 일 때만 진행(뿌요를 만나면 탈출)
 
                        --replace_row;
                    }
 
                    if (replace_row <= 0) replace_row = 0; // 음수가 나올 수 있으므로
                    
                    swap(map[replace_row][column], map[row][column]); // 블록 내리기(위치 교환)
                }
            }
        }
 
        if (changeBreak == 0) break; // changeBreak가 0이라는 것은 갱신된 뿌요가 없다는 뜻이므로, 탈출
 
        ++ans;
    }
 
    printf("%d\n", ans);
 
    return 0;
}