[SWEA] 5656번 벽돌 깨기

5656번 벽돌 깨기

문제 링크

 

해결방법

모든 경우에 대해 탐색하여 구현 하는 완전탐색 + 시뮬레이션 문제이다

 

 

⭐️ 솔루션 ⭐️

구슬은 총 4개를 발사할 수 있고, 가로의 최대 길이는 12 이므로 탐색에는 O(12^4) 의 시간이 걸린다

완전탐색은 DFS 로 구현하였고, 구슬이 파괴되는 과정은 BFS 를 통해 구현하였다

중력에 의해 벽돌을 내리는 로직을 설계하였는데, 테케 50개 중 49개만 맞아서 다른 코드를 참고해 로직을 변경하였다

 

 

소스코드

문제 해결 시간 : 2h

메모리 : 12652 KB

시간 : 1681 ms

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

struct node {
    int x,y,range;
    
    node() { }
    node(int _x,int _y,int _range) : x(_x),y(_y),range(_range) { }
};

int testcase;
int n,r,c,ans;

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

vector<vector<int>> map;

void printMap(vector<vector<int>> v){
    cout << "\n";
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cout << v[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

vector<vector<int>> bombBlock(vector<vector<int>> v,int col){
    // 구슬이 명중하는 노드 찾기
    int row = -1;
    for(int i=r-1; i>=0; i--){
        if(v[i][col] == 0){
            row = i;
            break;
        }
    }
    
    if(row == r-1) return v;
    else if(row == -1) row = 0;
    else row += 1;
    
    queue<node> q;
    q.push(node(row,col,v[row][col]));
    v[row][col] = 0;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int range = q.front().range;
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = x;
            int ny = y;
            for(int j=1; j<range; j++){
                nx += dx[i];
                ny += dy[i];
                
                if(nx<0 || ny<0 || nx>=r || ny>=c) continue;
                
                if(v[nx][ny]>=1){
                    q.push(node(nx,ny,v[nx][ny]));
                    v[nx][ny] = 0;
                }
            }
        }
    }
    
    return v;
}

vector<vector<int>> downBlock(vector<vector<int>> v){
    for(int i=r-1; i>=0; i--){
        for(int j=0; j<c; j++){
            if(v[i][j] != 0){
                int row = i;
                int col = j;
                
                while(1){
                    if(v[row+1][col]!=0 || row+1>=r) break;
                    
                    v[row+1][col] = v[row][col];
                    v[row][col] = 0;
                    row++;
                }
            }
        }
    }
    
    return v;
}

int getBlock(vector<vector<int>> v){
    int res = 0;
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(v[i][j] != 0) res++;
        }
    }
    
    return res;
}

void dfs(vector<vector<int>> v,int cnt){
    // n개의 구술을 쐈다면
    if(cnt == n){
        ans = min(ans,getBlock(v));
        return;
    }
    
    for(int i=0; i<c; i++){
        vector<vector<int>> tmp = bombBlock(v,i);
        tmp = downBlock(tmp);
        dfs(tmp,cnt+1);
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        cin >> n >> c >> r;
        
        map.clear();
        map.assign(r+1,vector<int>(c+1,0));
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                cin >> map[i][j];
            }
        }
        
        ans = INF;
        dfs(map,0);
        
        cout << "#" << tc << " " << ans << "\n";
    }
    
    return 0;
}