[BOJ] 백준 11559 Puyo Puyo

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

 Input 

......

......

......

......

......

......

......

......

.Y....

.YG...

RRYG..

RRYGG.

 

 Output 

3

① DFS 탐색을 통해 터질 수 있는 그룹을 찾아 폭파시킵니다.

    map[][]에서 각 지점별로 DFS 처리해야 합니다.

    ex) 아래는 총 2 그룹에서 터지지만 연쇄 횟수는 1번으로 측정됩니다.

..G.BB

..B.BB

RRRRGG

GGRRRR

 

② 폭파로 비워져 버린 공간을 채워야 합니다.

    한 개의 열을 기준으로 처리.

 

③ 터지는 뿌요가 없어질 때까지 ①, ② 과정 반복.

 

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include<queue>
using namespace std;
 
char map[12][6];
char visited[12][6];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
vector<pair<int, int>> bombList;
 
void DFS(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];
 
        // 배열 범위 내에서 재방문하지 않고
        // 빈공간이 아닌 같은 색깔인 경우만 DFS 탐색
        if (nextX < 0 || nextY < 0 || nextX >= 12 || nextY >= 6) continue;
        if (map[nextX][nextY] == '.') continue;
        if (visited[nextX][nextY]) continue;
        if (map[x][y] != map[nextX][nextY]) continue;
 
        visited[nextX][nextY] = true;
        bombList.push_back(make_pair(nextX, nextY));
        DFS(nextX, nextY);
    }
}
 
void rearrangeMap(){
        // 터질 수 있는 모든 그룹을 폭파 시킨 후 
        // 뿌요들이 아래로 내려가서 빈공간을 채우도록 처리
        for (int j = 0; j < 6; ++j) {
            for (int i = 11; i >= 0; --i) {
                // 빈 공간이 아닌 경우
                if (map[i][j] != '.') continue;
 
                int temp = i;
                // 빈 공간인 경우 위쪽에 빈공간이 아닌 뿌요를 가져와 내려오도록 구현.
                while (1) {
                    if (temp < 0) break;
                    if (map[temp][j] != '.') {
                        map[i][j] = map[temp][j];
                        map[temp][j] = '.';
                        break;
                    }
                    temp--;
                }
            }
        }
}
 
int main(void) {
    // input
    for (int i = 0; i < 12; ++i) {
        for (int j = 0; j < 6; ++j) {
            cin >> map[i][j];
        }
    }
 
    bool isBomb; // 폭파 여부 
    int answer = 0;
    while (1) {
        // 폭파 여부를 확인시 방문한 곳과 실제 폭파하는 곳을 저장
        isBomb = false;
        memset(visited, false, sizeof(visited));
        bombList.clear();
 
        // 모든 지점에 DFS
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; ++j) {
                // 방문하지 않으면서 빈공간이 아닌 경우
                if (!visited[i][j] && map[i][j] != '.') {
                    bombList.push_back(make_pair(i, j));
                    visited[i][j] = true;
                    DFS(i, j);
 
                    // 같은 색으로 인접한 뿌요가 4개이상인 경우
                    if (bombList.size() >= 4) {
                        // 적어도 한 그룹에서 폭파했으므로 표시
                        isBomb = true;
                        // 실제로는 폭파하는 그룹이 동시에 터진 후 뿌요들이 아래로 내려가서 빈공간이 채워지지만
                        // 폭파하는 그룹을 순차적으로 모두 처리한 후 뿌요들이 터진 공간을 채우도록 처리해도 무방
                        for (int i = 0; i < bombList.size(); i++) {
                            int x = bombList[i].first;
                            int y = bombList[i].second;
                            map[x][y] = '.';
                        }
                    }
                    bombList.clear();
                }
            }
        }
 
        rearrangeMap();
 
        if (isBomb == true) answer++;
        else break;
    }
 
    cout << answer << endl;
}