[C++] SWEA 5656 - 벽돌 깨기

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

SW Expert Academy

<풀이>

1. 구슬을 떨어트릴 위치를 정한다. 모든 경우를 탐색해야 하므로, 재귀함수를 이용한다.

2. 구슬을 떨어트리고, 시뮬레이션을 진행한다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct brick {
    //위치
    int x, y;
    //
    int cnt;
};
 
//4방향
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, W, H;
int map[15][12];
int tmpMap[15][12];
int ball[4];
int res;
 
void down() {
 
    //빈칸 위에 벽돌이 있을 경우, 벽돌 내리기
    for (int i = 0; i < W; i++) {
        //가장 아래칸부터 탐색
        for (int j = H - 1; j >= 0; j--) {
            if (tmpMap[j][i] == 0) {
                //빈칸 위에 벽돌이 있는 경우 -> 빈칸과 벽돌 위치 바꾸기
                for (int k = j - 1; k >= 0; k--) {
                    if (tmpMap[k][i] > 0) {
                        tmpMap[j][i] = tmpMap[k][i];
                        tmpMap[k][i] = 0;
                        break;
                    }
                }
            }
        }
    }
}
 
void go(int index) {
     
    //종료 조건 : 떨어트릴 구슬 위치 선택 완료
    if (index == N) {
 
        //초기화
        memcpy(tmpMap, map, sizeof(tmpMap));
        int cnt = 0;
 
        //N개 구슬 떨어트리기
        for (int i = 0; i < N; i++) {
 
            queue<brick> q;
 
            //구슬 떨어트리고, 가장 처음 터지는 벽돌 큐에 담기
            for (int j = 0; j < H; j++) {
                if (tmpMap[j][ball[i]] > 0) {
                    q.push({ j,ball[i],tmpMap[j][ball[i]] });
                    tmpMap[j][ball[i]] = 0;
                    break;
                }
            }
 
            //벽돌이 모두 터질때 까지 터트리기
            while (!q.empty()) {
 
                brick cur = q.front();
                q.pop();
 
                //4방향 모두 터트리기
                for (int j = 0; j < 4; j++) {
                    brick nxt = cur;
                    //(벽돌 길이 - 1) 만큼 터트리기
                    for (int k = 0; k < cur.cnt - 1; k++) {
 
                        nxt.x += di[j];
                        nxt.y += dj[j];
 
                        //범위를 넘어섰을 경우
                        if (nxt.x < 0 || nxt.y < 0 || nxt.x >= H || nxt.y >= W) {
                            break;
                        }
                        //벽돌이 아닐경우
                        if (tmpMap[nxt.x][nxt.y] == 0) {
                            continue;
                        }
 
                        //터지는 벽돌 큐에 담기
                        nxt.cnt = tmpMap[nxt.x][nxt.y];
                        q.push(nxt);
                        tmpMap[nxt.x][nxt.y] = 0;
                    }
                }
            }
 
            //벽돌 떨어트리기
            down();
        }
 
        //결과 계산 및 저장
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (tmpMap[i][j] > 0) {
                    cnt++;
                }
            }
        }
        if (res == -1 || cnt < res) {
            res = cnt;
        }
        return;
    }
 
    //떨어트릴 구슬 위치 저장(재귀함수)
    for (int i = 0; i < W; i++) {
        ball[index] = i;
        go(index + 1);
    }
 
    return;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        memset(tmpMap, 0, sizeof(tmpMap));
        memset(ball, 0, sizeof(ball));
        res = -1;
 
        //입력
        cin >> N >> W >> H;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cin >> map[i][j];
            }
        }
 
        //떨어트릴 구슬 위치 구하고, 결과값 저장
        go(0);
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
 
    return 0;
}

 

구현과 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.