[SWEA][모의 SW 역량테스트][C++] 5656 벽돌 깨기

문제

SWEA 모의 SW 역량테스트 - 5656 벽돌 깨기

SW Expert Academy

 

---

문제 풀이

접근 방식

구슬로 벽돌을 깨서 남은 벽돌의 개수가 최솟값이 되는 경우를 구하는 문제이다.

 

우선, 구슬을 놓을 위치를 정하기 위해 DFS 함수를 만들어주었다.

DFS 함수는 위치를 정해 shoot 함수를 시행하였고,

모든 구슬을 쏘았을 때, 남은 벽돌의 개수를 구하는 방식으로 구현하였다.

 

shoot 함수는 큐를 활용하여 터져야 하는 블록들을 저장하고, 큐 내에 존재하는 블록들을 모두 터뜨린 후,

블록들 간의 빈 공간을 제거해주는 과정을 수행하도록 구현하였다.

빈 공간은 아래에서부터 0의 위치를 세면서 그 개수만큼 아래로 이동시켜주는 방식으로 제거해주었다.

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct block {
    int x;
    int y;
    int p;
};
 
int N, W, H;
int board[15][12];
int temp_board[5][15][12];
int dir[4][2] = { {-1, 0},{0,1},{1,0},{0,-1} };
int down[15];
queue<block> q;
int MIN;
 
void shoot(int i, int cnt) {
    for (int j = 0; j < H; j++) {
        if (temp_board[cnt][j][i] == 0) continue;
        if (temp_board[cnt][j][i] == 1)
            temp_board[cnt][j][i] = 0;
        else
            q.push({ j, i, temp_board[cnt][j][i] - 1 });
        break;
    }
    if (q.empty()) return;
 
    int x, y, p, nx, ny;
    while (!q.empty()) {
        x = q.front().x, y = q.front().y, p = q.front().p, q.pop();
        temp_board[cnt][x][y] = 0;
        for (int a = 0; a < 4; a++) {
            nx = x, ny = y;
            for (int b = 0; b < p; b++)  {
                nx += dir[a][0];
                ny += dir[a][1];
                if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
                if (temp_board[cnt][nx][ny] <= 1)
                    temp_board[cnt][nx][ny] = 0;
                else
                    q.push({ nx, ny, temp_board[cnt][nx][ny] - 1 });
            }
        }
    }
 
    // 빈공간 제거
    for (int a = 0; a < W; a++) {
        memset(down, 0, sizeof(down));
        int move = 0;
        for (int b = H-1; b >= 0; b--) {
            if (temp_board[cnt][b][a] == 0) {
                move++;
            }
            else if(move != 0) {
                down[b] = move;
            }
        }
        for (int b = H - 1; b >= 0; b--) {
            if (down[b] != 0) {
                temp_board[cnt][b + down[b]][a] = temp_board[cnt][b][a];
                temp_board[cnt][b][a] = 0;
            }
        }
    }
}
 
void DFS(int cnt) {
    if (cnt == N) {
        // 남은 벽돌 개수 구하기
        int result = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (temp_board[cnt][i][j] != 0)
                    result++;
            }
        }
        if (MIN > result)
            MIN = result;
        return;
    }
 
    memcpy(temp_board[cnt + 1], temp_board[cnt], sizeof(board));
    for (int i = 0; i < W; i++)  {
        shoot(i, cnt + 1);
        DFS(cnt + 1);
        memcpy(temp_board[cnt + 1], temp_board[cnt], sizeof(board));
    }
}
 
int main(int argc, char** argv) {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기
        cin >> N >> W >> H;
        memset(board, 0, sizeof(board));
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> board[i][j];
            }
        }
 
        // 벽돌 깨기
        MIN = 987654321;
        memcpy(temp_board[0], board, sizeof(board));
        DFS(0);
 
        cout << "#" << test_case << " " << MIN << "\n";
    }
    return 0;
}

실행 결과

실행 결과 : Pass (159ms)