[C++] SWEA 5656 - 벽돌 깨기(2)

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

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

SW Expert Academy

<풀이>

1. 벽돌 보드를 입력받는다.

2. N개의 구슬을 쏘아서 가장 많은 벽돌이 제거되는 경우를 찾고, 그 때 남은 벽돌의 개수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 구슬을 쏘는 모든 경우를 다 해보아야 합니다. 따라서, 저는 브루트포스를 선택했습니다. 

 

2. 벽돌 깨트리기

=> 저는 DFS를 선택했습니다. 4방향을 벽돌의 power만큼 탐색하면서 벽돌을 깨트렸습니다. 사실 구현은 DFS, BFS 큰 상관이 없다고 생각합니다.

 

3. 벽돌 내리기

=> 벽돌을 깨트렸으면, 이제 벽돌을 빈공간으로 내려야합니다. 저는 큐(Queue)를 선택했습니다. 아래서 부터 벽돌인 것만 큐에 차례로 담고, 나중에 다시 벽돌을 쌓는 개념으로 구현하였습니다. 자세한 구현은 코드의 fallBrick() 함수를 참조해주세요.

 

4. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 구슬을 쏘는 위치는 재귀함수로 구현한다. 최악의 경우 12P4 이므로, 시간초과하지 않는다.

(2) 구슬의 위치를 다 결정하고 시뮬레이션을 할까, 구슬의 위치를 정할 때마다 시뮬레이션을 할까?

: 구슬의 위치를 정할 때마다 시뮬레이션을 진행한다. 구슬의 위치 [1,2,3,4]와 [1,2,3,5]는 구슬을 [1,2,3] 떨어트렸을 때까지 상황이 동일하다. 따라서, 시간을 줄이기 위해 구슬의 위치 정하고 바로 구슬을 떨어트려본다.

(3) 벽돌 깨트리는 것은 재귀함수로 구현한다.

(4) 벽돌 내릴 때는 큐를 이용해 구현한다.

(5) 남은 벽돌 개수의 최소를 구하는 것이므로, 반대로 얘기하면 깨트린 벽돌 개수의 최대를 구하는 것과 같다. 따라서, (처음 벽돌 개수) - (깨트린 벽돌 개수 max)를 출력한다.

자세한 구현은 아래 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#define INF 987654321
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, W, H;
int map[15][12];
int totalBricks;
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= H || y >= W) return false;
    return true;
}
 
int removeBrick(int x, int y) {
    int power = map[x][y];
    map[x][y] = 0;
    int ret = 1;
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j < power; j++) {
            int nx = x + (dx[i] * j);
            int ny = y + (dy[i] * j);
            if (!isInner(nx, ny)) break;
            if (map[nx][ny] > 0) {
                ret += removeBrick(nx, ny);
            }
        }
    }
    return ret;
}
 
void fallBrick() {
    for (int j = 0; j < W; j++) {
        queue<int> q;
        for (int i = H - 1; i >= 0; i--) {
            if (map[i][j] > 0) q.push(map[i][j]);
            map[i][j] = 0;
        }
        int col = H - 1;
        while (!q.empty()) {
            map[col][j] = q.front();
            q.pop();
            col--;
        }
    }
}
 
int simulation(int col) {
    int removedBricks = 0;
    for (int i = 0; i < H; i++) {
        if (map[i][col] > 0) {
            removedBricks = removeBrick(i, col);
            fallBrick();
            break;
        }
    }
    return removedBricks;
}
 
int selectBallPos(int cnt) {
    if (cnt == N) return 0;
 
    int ret = 0;
    int backup[15][12];
    memcpy(backup, map, sizeof(backup));
    for (int i = 0; i < W; i++) {
        int removedBricks = simulation(i);
        ret = max(ret, selectBallPos(cnt + 1) + removedBricks);
        memcpy(map, backup, sizeof(map));
    }
    return ret;
}
 
void solution() {
    answer = totalBricks - selectBallPos(0);
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0, W = 0, H = 0;
        memset(map, 0, sizeof(map));
        totalBricks = 0;
        answer = 0;
 
        //입력
        cin >> N >> W >> H;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> map[i][j];
                if (map[i][j] > 0) totalBricks++;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

브루트포스, DFS, 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.