[SWEA] 벽돌깨기

[SWEA] 벽돌깨기

Problem URL : 벽돌깨기

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define p pair<int,int>
using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int map[12][15];
int W, H;
int ans;

struct Node{
    int x;
    int y;
    int value;
    Node(int a,int b, int c): x(a), y(b), value(c){};
};


bool inRange(int x, int y){
    if(x < 0 || x >= W || y < 0 || y >= H)
        return false;
    return true;
}

void dfs(int shots){
    if( shots == 0 ){
        int sum = 0;
        for(int w=0; w<W; w++){
            for(int h=0; h<H; h++){
                if(map[w][h] != 0) sum++;
            }
        }
        if(ans > sum) {
            ans = sum;
        }
        return ;
    }
    
    int init_map[12][15];
   
    for(int w=0; w<W; w++) {
        for(int h=0; h<H; h++) {
            init_map[w][h] = map[w][h];
        }
    }

    for(int w=0; w<W; w++){
        queue<Node> q;
        for(int h=0; h<H; h++){
            if(map[w][h] != 0 ){
                q.push( Node(w, h, map[w][h]) );
                map[w][h] = 0;
                break;
            }
        }
     
        while (!q.empty()) {
            int x = q.front().x;
            int y = q.front().y;
            int value = q.front().value;
            q.pop();
            
            for(int d=0; d<4; d++){
                int nx = x;
                int ny = y;
                for(int i = 0; i < value-1; i++){
                    nx = nx + dx[d];
                    ny = ny + dy[d];
                    if(inRange(nx, ny) && map[nx][ny] != 0) {
                        q.push(Node(nx,ny, map[nx][ny]));
                        map[nx][ny] = 0;
                    }
                }
            }
        
        }
        
        for(int x = 0; x < W; x++){
            queue<int> q;
            
            for(int y = H - 1; y >= 0; y--){
                if(map[x][y] != 0) {
                    q.push(map[x][y]);
                    map[x][y] = 0;
                }
            } 
            int y = H - 1;
            while(!q.empty()) {
                map[x][y] = q.front();
                q.pop();
                y--;
            }

        } 

        dfs(shots - 1);
        
        for(int w=0; w<W; w++) {
            for(int h=0; h<H; h++) {
                map[w][h] = init_map[w][h];
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = 1e9;
        int shots;
        cin >> shots >> W >> H ;
        for(int h=0; h < H; h++){
            for(int w=0; w < W; w++){
                cin >> map[w][h];
            }
        }
        dfs(shots);
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}

Comments

실수가 많아서 오래걸렸다.
구현 자체는 어렵지 않은 문제