5656. [모의 SW 역량테스트] 벽돌 깨기

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

SW Expert Academy

 

[풀이 과정]

1. choose_brick(int idx) : 문제에서 주어진 N개의 벽돌을 선택하는 함수

- N개를 모두 골랐으면 count_brick()함수를 실행하여 남아있는 벽돌이 몇 개인지 구하고 result를 최솟값으로 갱신한다.

- N개를 아직 못골랐으면 0~W-1번째 값 중에 선택하고 break_brick(i)함수를 실행해 해당 열의 벽돌을 깬다. 이때 tmp 배열에 현재 상태를 저장해두었다가 재귀가 끝난 후 다음 탐색을 위해 원래 상태로 돌려놓는다. 

 

2. break_brick(int col) : col 열의 벽돌을 깨는 함수

- 깨질 벽돌을 저장할 큐를 하나 만든다.

- col열에서 가장 위에 있는 벽돌이 무엇인지 찾아서 큐에 넣고 해당 벽돌은 0으로 바꾼다. 

- 큐에 있는 값들을 하나씩 꺼내서 탐색을 시작한다.

- 이때 (arr[x][y]-1)만큼 상하좌우 벽돌들도 깨지기 때문에 아래와 같이 2중 반복문을 통해 nx, ny를 구했다.

- nx, ny가 배열을 넘어가거나 0이면 따로 처리할 필요가 없으므로 continue한다.

- 위 조건이 아니면 모두 깨져야하는 벽돌이기 때문에 큐에 넣어주고 해당 위치도 0으로 바꾼다.

- 이후 gravity()함수를 실행해 벽돌을 아래로 내려 빈 공간을 채워준다.

 

3. gravity() : 빈 공간이 있을 경우 벽돌을 밑으로 떨어트리는 함수

- 각 열에 대해 배열의 바닥부터 시작해서 0인 곳(빈칸)을 찾는다.

- 빈칸을 찾으면 그 행부터 0번 행까지 거꾸로 벽돌이 있는지 찾는다.

- 벽돌이 있으면 빈칸에 벽돌을 채우고 원래 벽돌은 0으로 바꿔준다.

- 모든 열에 대해 위 과정을 반복한다.

 

4. count_brick(): 남은 벽돌의 개수를 세는 함수

- 전체 배열을 탐색하면서 0보다 큰 곳(벽돌)이 몇 개인지 센다.

 

5. 각 테스트 케이스에 대해 result를 출력한다. (테스트 케이스마다 초기화를 잊으면 안된다!)

---

[소스 코드]

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 20;
const int INF = 987987987;

int T, N, W, H, arr[MAX][MAX], result;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
struct INFO{
    int x, y, val;
};

int count_brick(){
    int cnt = 0;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(arr[i][j] > 0) cnt++;
        }
    }
    return cnt;
}

void save_state(int A[MAX][MAX], int B[MAX][MAX]){
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++) A[i][j] = B[i][j];
    }
}

void gravity(){
    for(int j=0;j<W;j++){
        for(int i=H-1;i>0;i--){
            if(arr[i][j] == 0){
                for(int k=i-1;k>=0;k--){
                    if(arr[k][j] > 0){
                        arr[i][j] = arr[k][j];
                        arr[k][j] = 0;
                        break;
                    }
                }
            }
        }
    }
}

void break_brick(int col){
    queue <INFO> q;

    for(int i=0;i<H;i++){
        if(arr[i][col] > 0){
            q.push({i, col, arr[i][col]});
            arr[i][col] = 0;
            break;
        }
    }

    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int val = q.front().val;
        q.pop();

        for(int i=1;i<val;i++){
            for(int j=0;j<4;j++){
                int nx = x + dx[j]*i;
                int ny = y + dy[j]*i;
                if(nx < 0 || nx >= H || ny < 0 || ny >= W || arr[nx][ny] == 0) continue;
                q.push({nx, ny, arr[nx][ny]});
                arr[nx][ny] = 0;
            }
        }
    }
    gravity();
}

void choose_brick(int idx){
    if(idx >= N){
        int cur_cnt = count_brick();
        result = min(result, cur_cnt);
    }
    else{
        for(int i=0;i<W;i++){
            int tmp[MAX][MAX] = {0};
            save_state(tmp, arr);
            break_brick(i);
            choose_brick(idx+1);
            save_state(arr, tmp);
        }
    }
}

int main(){
    scanf("%d", &T);

    for(int t=1;t<=T;t++){
        memset(arr, 0, sizeof(arr));
        result = INF;
        scanf("%d %d %d", &N, &W, &H);

        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                scanf("%d", &arr[i][j]);
            }
        }
        choose_brick(0);
        printf("#%d %d\n", t, result);
    }
    return 0;
}