[코드트리] 2차원 폭발 게임 C++

문제

https://www.codetree.ai/missions/2/problems/The-2D-bomb-game?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획세우기

아래 과정을 더이상 터트릴 것이 없을 때까지 반복

1. m개 이상인 구역을 0으로 바꾼다.
2. 중력적용(아래shift)

Rotation은 아래와 같이 표를 그려서 규칙을 찾았다

Rotation후 중력을 적용하고

 

또 m개 이상의 연속된 원소가 없을 때까지 Explode와 Drop을 반복해준다.

 

풀이

#include <iostream>

using namespace std;

int n, m ,k;// m개 이상
int arr[101][101];

void Roatate(){
    int tmp[101][101]={0, };
    for(int row=0; row<n; row++){
        for(int col=0; col<n; col++){
            tmp[col][n-row-1]=arr[row][col];
        }
    }

    // tmp를 다시 arr에 복사
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            arr[i][j]=tmp[i][j];
        }
    }
}

void Drop(){
    for(int col=0; col<n; col++){
        // col번째 열에서 가장 아래 행에 있는 0 찾기
        int endOfIdx = -1;
        for(int row=n-1; row>0; row--){
            if(arr[row][col]==0) {
                endOfIdx=row;
                break;
            }
        }
        // 0이 없는 열이라면 그냥 넘어가기
        if(endOfIdx==-1) continue;

        // Swap
        for(int row=endOfIdx-1; row>=0; row--){
            if(arr[row][col]!=0){
                arr[endOfIdx][col]= arr[row][col];
                arr[row][col]=0;
                endOfIdx--;
            }
        }
    }
}

void Explode(){
    for(int col=0; col<n; col++){
        int cnt=1;
        for(int row=0; row<n-1; row++){
            if(arr[row][col]==arr[row+1][col]) {
                cnt++;
                continue;
            }

            if(cnt>=m){
                for(int idx=row-cnt+1; idx<=row; idx++){
                    arr[idx][col]=0;
                }
            }
            cnt=1;
        }

        if(cnt>=m){
            for(int idx=(n-1)-cnt+1; idx<=n-1; idx++){
                arr[idx][col]=0;
            }
        }
    }
}

bool PossibleToExplode(){
    for(int col=0; col<n; col++){
        int cnt=1;
        for(int row=n-1; row>=0; row--){
            if(arr[row][col]==0 || row-1<0) break;

            if(arr[row][col]==arr[row-1][col]) cnt++;
            else cnt=1;

            if(cnt>=m) return true;
        }
    }
    return false;
}
void PrintArr(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << arr[i][j] <<" ";
        }
        cout <<'\n';
    }
}

int main() {
    cin >> n >> m >> k;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
        }
    }

    // solution
    if(m==1){
        cout << 0 <<'\n';
        exit(0);
    }

    for(int i=0; i<k; i++){
        while(PossibleToExplode()){
            Explode();
            Drop();
        }


        Roatate();
        Drop();

        while(PossibleToExplode()){
            Explode();
            Drop();
        }
    }

    // output
    int answer=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(arr[i][j]!=0) answer++;
        }
    }
    cout << answer<<'\n';
    return 0;
}