[SW Expert 5656] 벽돌 깨기

#문제 

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

#풀이

전체적인 틀은 완전 탐색을 통하여 풀었다.

구슬의 개수가 4개에 맵의 전체 크기가 12X15 이였고, 구슬을 떨어트릴때는 W만 보면 되기 때문에 완탐이 가능하다.

처음에 구슬이 블록을 터트렸을때 어떻게 해야될지 고민을 많이 했고, 시간도 많이 잡아 먹었다.

BFS가 바로 떠올랐지만, 구현하는데에도 많은 시간이 걸렸다. 

많은 연습만이 살길이다!....

먼저 어떠한 위치에 구슬을 떨어트리고 위치에서의 맵의 값이 0이면 다시 자신을 호출하여 다음 칸으로 이동한다.

만약 0이 아닌 점을 만나게 되면, 큐에 넣는다. 그 후에 4방향(방향마다 쭈욱!) 으로 탐색을 하다 0이 아닌 값이 나온다면, 해당 값을 큐에 넣는다. 

이때, 해당 맵의 값을 0으로 만들어주었다. 다른 곳에서 터졌을때, 또 터지는 것을 방지하기 위해서이다.

모든 블럭들이 터지고난 뒤에는 맵을 정리해주어야 한다.

이때는 줄마다 0이 아닌 값을 큐에 넣고(반대로!! FIFO!이기때문! 큐 말고도 다른것을 사용해도 된다.) 해당 위치를 모두 0으로 만든뒤에 다시 밑에서부터 큐가 비워질 때까지 맵에 쌓았다.

완탐이기 때문에 꼭 이전 상태의 맵을 저장한뒤에 다시 돌리는 것을 까먹지 말자.

주의 할 점!

내가 멍청해서 일지는 몰라두... 꼭! W와 H를 헷갈리지 말자...

또, 구슬을 떨어트렸을 때 해당 위치에 블럭이 없을 경우에는 꼭 예외처리를 해주어야한다. 주의하자!

그럼에도 엄청 나게 많이 틀렸다. 테케 50개중 47개만 맞았는데, 한참을 헤맸다...

이유는 구슬을 떨어트리는 위치가 잘못된 것이다.

시작 부분에서 부터 떨어트렸는데 그것이 큰 잘못이였다.

따라서 맵을 12X16으로 만들고 맵을 받을 때는 1~H까지 받고, 구슬의 시작 위치는 0으로 해놓으니 통과하였다 :(

단순한 문제인줄 알았지만... 얕잡아 보면 안된다! 라는것을 깨닫는 문제였다.

#코드

#include <iostream>
#include <queue>
#include <cstring>
#define INF 987654321
 
using namespace std;
 
int N, W, H;
int map[16][12];
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
int ans = INF;
 
void copyMap(int (*a)[12], int(*b)[12]){
    for(int i = 1; i <= H; i++){
        for(int j = 0; j < W; j++){
            b[i][j] = a[i][j];
        }
    }
}
 
void blockSort(){
    for(int i = 0; i < W; i++){
        queue<int> block;
        for(int r = H; r > 0; r--){
            if(map[r][i] > 0){
                block.push(map[r][i]);
            }
        }
        for(int r = 1; r <= H; r++) map[r][i] = 0;
        int h = H;
        while(!block.empty()){
            int range = block.front();
            block.pop();
            map[h][i] = range;
            h--;
        }
    }
}
 
void dropTheBall(int r, int c, int range){
    if(range == 0){
        if(r+1 > H) return;
        dropTheBall(r+1, c, map[r+1][c]);
    }else{
        queue<pair<pair<int, int>,int>> bombs;
        bombs.push({{r,c},range});
        map[r][c] = 0;
        while(!bombs.empty()){
            int curR = bombs.front().first.first;
            int curC = bombs.front().first.second;
            int curRange = bombs.front().second;
            bombs.pop();
            map[curR][curC] = 0;
            for(int i = 1; i < curRange; i++){
                for(int j = 0; j < 4; j++){
                    int nr = curR + i*dr[j];
                    int nc = curC + i*dc[j];
                    if(nr < 1 || nr > H || nc < 0 || nc > W-1)
                        continue;
                    if(map[nr][nc] > 0){
                        bombs.push({{nr,nc},map[nr][nc]});
                        map[nr][nc] = 0;
                    }
                }
            }
        }
        blockSort();
    }
}
 
void playball(int n){
    if(n == 0){
        int sum = 0;
        for(int i = 1; i <= H; i++){
            for(int j = 0; j < W; j++){
                if(map[i][j] > 0) sum++;
            }
        }
        if(ans > sum) ans = sum;
        return;
    }
    int copyM[16][12];
    for(int i = 0; i < W; i++){
        copyMap(map, copyM);
        dropTheBall(0,i,0);
        playball(n-1);
        copyMap(copyM, map);
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    int tc;
    cin >> tc;
    for(int t = 1; t <= tc; t++){
        memset(map, 0, sizeof(map));
        cin >> N >> W >> H;
        for(int i = 1; i <= H; i++){
            for(int j = 0; j < W; j++){
                cin >> map[i][j];
            }
        }
        ans = INF;
        playball(N);
        cout << "#" << t <<" "<< ans << endl;
    }
    return 0;
}