[swea] 벽돌깨기

가장 위에 있는 벽돌에 구슬이 떨어지면서 벽돌의 숫자만큼 사방으로 깨진다. dfs를 이용한 백트레킹으로 큰 틀을 잡았고, 벽돌을 깨는 함수와 깬 이후 벽돌들을 맨 밑으로 이동시키는 함수를 작성하였다.

벽돌을 깰때, 벽돌이 0이 아니면 재귀함수를 통해 모든 벽돌을 깨고, 벽돌을 이동할 때는 큐를 사용해 배열의 맨 밑으로 쌓아주었다.

#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
 
int dxy[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int n, w, h;
int answer = 10000;
vector<vector<int>> map;
 
void remo(int x, int y, int num) {
    if (map[x][y] == 3)
        cout << "";
 
    map[x][y] = 0;
    for (int i = 0; i < 4; i++) {
        int nx = x;
        int ny = y;
        for(int j = 0; j <num - 1; j++) {
            nx += dxy[i][0];
            ny += dxy[i][1];
 
            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                continue;
            if (map[nx][ny] >= 1)
                remo(nx, ny, map[nx][ny]);
        }
    }
}
void moveblock() {
    queue<int> q;
    for (int i = 0; i < w; i++) {
        int tmp = h - 1;
        for (int j = h - 1; j >= 0; j--) {
            if (map[j][i] != 0) {
                q.push(map[j][i]);
                map[j][i] = 0;
            }
        }
        while (!q.empty()) {
            map[tmp][i] = q.front();
            tmp--;
            q.pop();
        }
    }
    
}
 
void dfs(int depth) {
    if (depth == n) {
        int tmp = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] != 0) {
                    tmp++;
                }
            }
        }
        if (tmp == 4) {
            cout << "";
        }
        answer = answer < tmp ? answer : tmp;
        return;
    }
    int a;
    vector<vector<int>> tmp;
 
    for (int i = 0; i < w; i++) {
        tmp = map;
 
        a = 0;
        while(map[a][i] == 0) {
            a++;
            if (a == h - 1)
                break;
        }
 
        if (map[a][i] >= 1) {
            remo(a, i, map[a][i]);
        }
        moveblock();
        dfs(depth + 1);
        map = tmp;
    }
}
int main(int argc, char** argv)
{
    int test_case;
    int T;
 
    //freopen("input.txt", "r", stdin);
    cin >> T;
    
    for (test_case = 1; test_case <= T; ++test_case)
    {
        cin >> n >> w >> h;
 
        map.assign(h,vector<int>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
            }
        }
 
        dfs(0);
 
        cout << "#" << test_case << " " << answer << endl;
        answer = 1000;
    }
    return 0;
}