[BaekJoon/백준] 11559번 Puyo Puyo

 

 

문제를 읽고, 정의했다.

 

1 phase : 제거할 것 체크 한 뒤에 제거 + 중력 내리는 작업

 

 

dfs 함수를 돌면서, 인접 갯수가 4개가 넘는지 헤아린 뒤,

4개 넘으면 BBOM 함수(마찬가지로 dfs형식)를 통해 제거할 것으로 체크시킨다.

 

그 뒤에 for문으로 제거해주며

 

제거를 완료하면 중력으로 내리는 작업을 해준다.

 

내리는 작업은 맨 아래 행부터 체크하기 시작하며,

어디까지 내릴 수 있을지 체크하는 것도 맨 아래 행부터 체크하면 수월하다.

/*
 
 1 phase : 터지는 작업 + 내리는 작업
 
 */


#include <iostream>
#include <cstring>

using namespace std;


char MAP[12][6];
bool VISIT[12][6];
bool BOOM[12][6]; // 터질 곳

int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

int PHASE, CNT; // PHASE : 전체 횟수. CNT : 인접 갯수
bool flag; // 파괴 작업이 현재 PHASE에 한번이라도 있다면 true

void dfs(int x, int y) {
    
    
    VISIT[x][y] = true;
    CNT++;
    
    
    for(int i = 0; i < 4; i++) {
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        if(tx < 0 || tx >= 12 || ty < 0 || ty >= 6)
            continue;
        
        if(!VISIT[tx][ty] && MAP[tx][ty] == MAP[x][y])
            dfs(tx, ty);
        
    }
}

void BBOM(int x, int y) {
    
    
    BOOM[x][y] = true;
    
    for(int i = 0; i < 4; i++) {
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        if(tx < 0 || tx >= 12 || ty < 0 || ty >= 6)
            continue;
        
        if(!BOOM[tx][ty] && MAP[tx][ty] == MAP[x][y])
            BBOM(tx, ty);
        
    }
}



int main() {
    
    
    for(int i = 0; i < 12; i++) {
        for(int j = 0; j < 6; j++)
            cin >> MAP[i][j];
    }
    
    
    while(1) {
                
        flag = false;
        memset(VISIT, 0, sizeof(VISIT));
        memset(BOOM, 0, sizeof(BOOM));
        
        // 터질 위치 체크
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 6; j++) {
                
                if(!VISIT[i][j] && MAP[i][j] != '.') {
                    CNT = 0; // 인접 갯수
                    dfs(i, j); // 인접 갯수 체크
                    
                    if(CNT >= 4) { // 인접 갯수가 4개가 넘는다면
                        flag = true;
                        BBOM(i, j); // 터질 위치로 인지하고 처리.
                    }
                }
            }
        }
        
        
        if(!flag)
            break;
        
        PHASE++;

        // 터짐
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 6; j++) {
                if(BOOM[i][j]) {
                    MAP[i][j] = '.';
                }
            }
        }
        
        
        // 내리는 작업
        // 행의 맨 아래에서부터 해야겠지
        for(int i = 11; i >= 0; i--) {
            
            for(int j = 0; j < 6; j++) {
                
                if(MAP[i][j] != '.') {
                    
                    // 행의 맨 아래에서부터 점인 곳을 찾아서 바로 넣어줌. 순간이동인 격. 더 빠를듯.
                    for(int k = 11; k > i; k--) {
                        
                        if(MAP[k][j] == '.') {
                            swap(MAP[i][j], MAP[k][j]);
                            break;
                        }
                    }
                }
            }
        }
    }
    
    
    cout << PHASE << "\n";
    
}

 

 

소요 시간 : 50분