[소프트웨어 익스퍼트 아카데미][SWEA][모의 SW 역량테스트][ C++][5656번] 벽돌 깨기

dfs를 이용해서 구슬이 떨어지는 위치를 조정하였습니다.

#include<iostream>
#include<queue>
using namespace std;
struct q_info {
    int x;
    int y;
    int bomb_size;
};
 
int ans;
int cnt;
int N, W, H;
int brick[16][13];
queue<q_info> q;
 
void init() {
    ans = 987654321;
    cnt = 0;
    for (register int Y = 1; Y <= 15; Y++) {
        for (register int X = 1; X <= 12; X++) {
            brick[Y][X] = 0;
        }
    }
    while (!q.empty()) {
        q.pop();
    }
}
 
void move_brick() {
    for (register int X = 1; X <= W; X++) {
        for (register int Y = H; Y > 0; Y--) {
            if (brick[Y][X] == 0) {
                for (register int y = Y; y > 0; y--) {
                    if (brick[y][X] > 0) {
                        brick[Y][X] = brick[y][X];
                        brick[y][X] = 0;
                        break;
                    }
                }
            }
        }
    }
}
 
void bomb_func() {
    while (!q.empty()) {
        q_info cur = q.front();
        q.pop();
        int x = cur.x;
        int y = cur.y;
        int b_s = cur.bomb_size;
        for (int X = 1; X <= b_s; X++) {
            if (X + x <= W) {
                if (brick[y][x + X] == 1) {
                    brick[y][x + X] = 0;
                }
                else if(brick[y][x+X]>1) {
                    q_info next;
                    next.x = x + X;
                    next.y = y;
                    next.bomb_size = brick[y][x + X] - 1;
                    q.push(next);
                    brick[y][x + X] = 0;
                }
            }
            if (x - X > 0) {
                if (brick[y][x - X] == 1) {
                    brick[y][x - X] = 0;
                }
                else if (brick[y][x - X]>1) {
                    q_info next;
                    next.x = x - X;
                    next.y = y;
                    next.bomb_size = brick[y][x - X] - 1;
                    q.push(next);
                    brick[y][x - X] = 0;
                }
            }
        }
        for (int Y = 1; Y <= b_s; Y++) {
            if (y + Y <= H) {
                if (brick[y + Y][x] == 1) {
                    brick[y + Y][x] = 0;
                }
                else if (brick[y + Y][x]>1) {
                    q_info next;
                    next.x = x;
                    next.y = y + Y;
                    next.bomb_size = brick[y + Y][x] - 1;
                    q.push(next);
                    brick[y + Y][x] = 0;
                }
            }
            if (y - Y > 0) {
                if (brick[y - Y][x] == 1) {
                    brick[y - Y][x] = 0;
                }
                else if (brick[y - Y][x]>1) {
                    q_info next;
                    next.x = x;
                    next.y = y - Y;
                    next.bomb_size = brick[y - Y][x] - 1;
                    q.push(next);
                    brick[y - Y][x] = 0;
                }
            }
        }
    }
    move_brick();
}    
 
void find_bomb(int X) {
    
    for (register int Y = 1; Y <= H; Y++) {
        if (brick[Y][X] > 0) {
            if (brick[Y][X] == 1) {
                brick[Y][X] = 0;
                break;
            }
            if(brick[Y][X]>1) { //1보다 크다면
                q_info INFO;
                INFO.x = X;
                INFO.y = Y;
                INFO.bomb_size = brick[Y][X] - 1;
                q.push(INFO);
                brick[Y][X] = 0;
                bomb_func();
                break;
            }
        }
    }
}
 
void dfs_pos(int dep) {
    if (dep == N) {
        for (register int Y = 1; Y <= H; Y++) {
            for (register int X = 1; X <= W; X++) {
                if (brick[Y][X] > 0)
                    cnt++;
            }
        }
        
        if (ans > cnt) ans = cnt;
        cnt = 0;
        return;
    }
    
    for (register int pos = 1; pos <= W; pos++) {
        int brick_temp[16][13];
        for (register int Y = 1; Y <= H; Y++) {
            for (register int X = 1; X <= W; X++) {
                brick_temp[Y][X] = brick[Y][X];
            }
        }
            find_bomb(pos);
            dfs_pos(dep + 1);
            for (register int Y = 1; Y <= H; Y++) {
                for (register int X = 1; X <= W; X++) {
                    brick[Y][X] = brick_temp[Y][X];
                }
            }
        
 
    }//X
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T;
    scanf("%d", &T);
    //cin >> T;
    for (int t = 1; t <= T; t++) {
        init();
        scanf("%d %d %d", &N, &W, &H);
        //cin >> N >> W >> H;
        for (register int Y = 1; Y <= H; Y++) {
            for (register int X = 1; X <= W; X++) {
                scanf("%d", &brick[Y][X]);
            }
        }
        dfs_pos(0);
        printf("#%d %d\n", t, ans);
        //cout << "#" << t << " " << ans << endl;
    }
}