SW Expert Academy 5656. 벽돌 깨기

문제

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

걸린 시간

-

풀이

C++

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#define INF 987654321
using namespace std;

int n, w, h;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

void shot(int y, int x, int space[15][12], vector<vector<int>>& visited){
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    while(!q.empty()){
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
        if(visited[cy][cx]) continue;
        visited[cy][cx] = 1;
        for(int i = 0; i < 4; i++){
            int ny = cy;
            int nx = cx;
            for(int j = 0; j < space[cy][cx]-1; j++){
                ny += dy[i];    
                nx += dx[i];
                if(0 <= ny && ny < h && 0 <= nx && nx < w)
                    if(space[ny][nx] > 0)
                        q.push(make_pair(ny, nx));
            }
        }
    }
}

int solve(int space[15][12], vector<vector<int>> brick, int N){
    // 기저 사례
    if(N == n){
        int cnt = 0;
        for(int y = 0; y < h; y++)
            for(int x = 0; x < w; x++)
                if(space[y][x] > 0) cnt++;
        return cnt;
    }
    // 재귀 호출
    int ret = INF;
    for(int i = 0; i < brick.size(); i++){
        if(brick[i].size() == 0) continue;
        int s[15][12];
        auto b = brick;
        memset(s, 0, sizeof(s));
        vector<vector<int>> visited(h, vector<int>(w, 0));
        shot(h-brick[i].size(), i, space, visited);
        // remove brick
        for(int y = 0; y < h; y++)
            for(int x = 0; x < w; x++)
                if(space[y][x] > 0 && visited[y][x]) b[x].erase(b[x].begin()+h-y-1);
        // update brick
        for(int x = 0; x < w; x++)
            for(int y = 0; y < b[x].size(); y++)
                s[h-y-1][x] = b[x][y];
        int cand = solve(s, b, N+1);
        ret = min(ret, cand);
    }
    return ret;
}

int main()
{
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> n >> w >> h;
        // init
        int space[15][12];
        vector<vector<int>> brick;
        memset(space, 0, sizeof(space));
        brick.resize(w);
        for(int y = 0; y < h; y++)
            for(int x = 0; x < w; x++)
                cin >> space[y][x];
        for(int y = h-1; y >= 0; y--)
            for(int x = 0; x < w; x++)
                if(space[y][x] > 0) brick[x].push_back(space[y][x]);
        int ans = solve(space, brick, 0);
        if(ans == INF) cout << "#" << test_case << " " << 0 << "\n";
        else cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;
}

구슬을 부딪혀 없앨 수 있는 최대 벽돌의 개수를 구하려면 모든 경우를 조사해보아야 한다.

구슬을 최대 4번 쏠 수 있고 벽돌이 있는 공간의 크기도 최대 15x12 로 작기 때문에 완전탐색이 가능하다. 최악의 경우 깊이가 4이고, 자식이 한 노드당 12개인 트리 형태의 구조를 띈다.