[코드트리] 십자 모양의 지속적 폭발 C++

문제

https://www.codetree.ai/missions/2/problems/cross-shape-continuous-bomb?&utm_source=clipboard&utm_medium=text

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

 

계획세우기

폭발시킬 열이 주어지면 row를 0부터 살펴보면서 배열에 0이면 다음 row를 살펴보고 아니면 해당 bomb[row][col]에 적힌 숫자만큼 폭발 시킨다.

폭발 시킨 후에는 다음 row를 보면 안 되기 때문에 break를 걸어서 다음 열을 폭발시키지 않도록 해준다.

폭발한 후에는 배열을 아래 방향으로 떨어트려준다.

떨어트리는 방법에 대해서는 1차원 젠가 글을 참고!

풀이

#include <iostream>

using namespace std;

int n, m;
int bombs[201][201];
int explodeCol[11];

// Down Shift
void Drop(){
    for(int col=0; col<n; col++){
        int endOfIdx=-1;
        // 아래에서부터 0인 칸 찾기
        for(int row=n-1; row>0; row--){
            if(bombs[row][col]==0){
                endOfIdx=row;
                break;
            }
        }
        if(endOfIdx==-1) continue;

        // 위로 올라가면서 0이 아닌 칸이랑 자리 바꾸기
        for(int row=endOfIdx-1; row>=0; row--){
            if(bombs[row][col]!=0){
                bombs[endOfIdx][col]=bombs[row][col];
                bombs[row][col]=0;
                endOfIdx--;
            }
        }
    }
}

void Explode(int column){
    // 좌(0,-1) 상(-1,0) 우(0,1) 하(1,0)
    int dx[4]={0, -1, 0, 1};
    int dy[4]={-1, 0, 1, 0};

    for(int row=0; row<n; row++){
        if(bombs[row][column]==0)continue;
        for(int dir=0; dir<4; dir++){
            // range 범위: 1이면 자기칸만 터지고 2면 주변 1칸 터져야 하니까
            for(int range=1; range<bombs[row][column]; range++){
                int nx=row+dx[dir]*range;
                int ny=column+dy[dir]*range;
                if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
                bombs[nx][ny]=0;
            }
        }
        bombs[row][column]=0;
        break;
    }
}

int main() {
    // input
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> bombs[i][j];
        }
    }
    for(int i=0; i<m; i++){
        cin >> explodeCol[i];
    }

    // Solution
    for(int i=0; i<m; i++){
        Explode(explodeCol[i]-1);
        Drop();    
    }

    // output
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << bombs[i][j] << " ";
        }
        cout <<'\n';
    }
    return 0;
}