[SW Expert Academy] 5656. 벽돌 깨기

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define p pair<int,int>
using namespace std;

// 동 서 남 북
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int map[20][15];
int n,m;
int ans;

struct Node{
    int x;
    int y;
    int value;
    Node(int a,int b, int c): x(a), y(b), value(c){};
};


bool inRange(int x, int y){
    if(x < 0 || x >=n || y < 0 || y >= m)
        return false;
    return true;
}

void print(){ // for Debugging
    for(int i=0; i<n; i++){
        if( i % 5 == 0)
            cout << endl;
        for(int j=0; j<m; j++){
            cout << map[i][j] << "  ";
        }
        cout << endl;
    }
    cout << "========================" << endl;
}

/*
 1번 구술 쏘고 맵 합치기
 */
void merge(){
    for(int i=0; i<m; i++){
        queue<int> q;
        /*
         해당 컬럼에서
         가장 아래에 있는 값부터 큐에 삽입
         */
        for(int j=n-1; j>=0; j--){
            if(map[j][i] != 0)
                q.push(map[j][i]);
        } // end of for j
        
        
        /*
         바로 밑에 for문에서
         q.front()를 돌릴 때
         런타임 에러가 발생나지 않도록
         row의 최대값 15만큼 큐에 삽입한다.
         
         더 자세하게 말하자면
         컬럼이 [ 1 1 0 1 1 ] 들어있다면
         
         밑에 for문은 row 수(=5) 만큼 돈다.
         그런데 큐에 사이즈는 4이므로
         j가 n-1부터 시작해서 0이 되었을 때 큐는 비어있고
         이 때 q.front()접근을 하게 되면 에러가 발생한다.
         
         이런 경우를 방지하기 위해
         row의 최대 값인 15개를 큐에 삽입한다.
         주의할 점은 큐는 FIFO이므로
         0이 아닌 값을 위에 for문에서 미리 넣어주고
         그 후 row의 최대 값만큼 0을 삽입한다.
         
         그래야지 가장 아래(j=n-1)부터 올바른 값이 쌓이고
         그 위로는 0이 삽입된다.
         */
        for(int k=0; k<15; k++)
            q.push(0);
        
        /*
         새로운 값으로 해당 컬럼을 셋팅
         */
        for(int j=n-1; j>=0; j--){
            map[j][i] = q.front();
            q.pop();
        }
    } // end of for i
}

/*
 남아있는 벽돌의 수 카운팅
 */
int chk(){
    int cnt = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(map[i][j] != 0)
                cnt++;
        }
    }
    return cnt;
}

void pinbol(int col_idx){
    queue<Node> q;
    for(int i=0; i<n; i++){
        if(map[i][col_idx] != 0 ){
            /*
             값이 1이라면 자신을 제외한 상하좌우 0칸씩 포함
             값이 3이라면 자신을 제외한 상하좌우 2칸씩 포함
             값이 i라면 자신을 제외한 상하좌우 i-1칸씩 포함
             그러므로 값 - 1 을 넣어준다.
             */
            q.push( Node(i,col_idx, map[i][col_idx] - 1) );
            map[i][col_idx] = 0;
            break;
        }
    } // end of for i
    
    
    while (! q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int value = q.front().value;
        q.pop();
        
        /*
         체크해야하는 값만큼
         상하좌우 살핀다.
         */
        for(int i=0; i<4; i++){
            int nx = x;
            int ny = y;
            for(int j=0; j<value; j++){
                nx = nx + dx[i];
                ny = ny + dy[i];
                if( ! inRange(nx, ny)) continue;
                if( map[nx][ny] != 0)
                    q.push( Node(nx,ny, map[nx][ny] - 1) );
                map[nx][ny] = 0;
            } // end of for j
        } // end of for i
        
    } // end of while
    
    /*
     부수는 작업이 끝나면
     바뀐 맵으로 바꾸는 작업 실시
     */
    merge();
//    print();
}

void dfs(int break_cnt){
    if( break_cnt == 0 ){
        int _ans = chk();
        ans = ans < _ans ? ans : _ans;
        return ;
    }
    
    int tmp_map[20][15];
    /*
     DFS이므로
     기존의 맵을 갖고 있어야 한다.
     */
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) tmp_map[i][j] = map[i][j];
    for(int i=0; i<m; i++){
        pinbol(i);
        dfs(break_cnt - 1);
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) map[i][j] = tmp_map[i][j];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int TC;
    cin >> TC;
    
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        ans = 2e9;
        int cnt;
        cin >> cnt >> m >> n ;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cin >> map[i][j];
            }
        }
        dfs(cnt);
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#define p pair< pair<int,int> ,int>
using namespace std;

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

int map[15][12];
int sub_map[15][12];
int ans;
int row,col;

void merge_map(){
    for(int c=0; c<col; c++){
        int tmp_col[15] = {0,};
        int idx = 0;
        
        for(int r=row-1; r>=0; r--){
            if(map[r][c] != 0){
                tmp_col[idx] = map[r][c];
                idx++;
            }
        }
        
        idx = 0;
        for(int r=row-1; r>=0; r--){
            map[r][c] = tmp_col[idx];
            idx++;
        }
    
    }
}

int cal(){
    int cnt = 0 ;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(map[i][j])
                cnt++;
        }
    }
    return cnt;
}
bool inRange(int x, int y){
    if( x < 0 || x >= row || y < 0 || y >= col)
        return false;
    return true;
}

void work(int st_col){
    for(int i=0; i<row; i++){
        if(map[i][st_col] == 0)
            continue;
        
        queue<p> q;
        q.push({ {i,st_col}, map[i][st_col] });
        
        int v[15][12] = {0,};
        v[i][st_col] = 1;
        
        while (! q.empty()) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int value = q.front().second - 1; // 자기 자신은 이미 포함했으니 -1
            q.pop();

            map[x][y] = 0;
            for(int j=1; j<=value; j++){
                int nx = x + j;
                if(inRange(nx, y)){
                    if(map[nx][y] != 0 && v[nx][y] == 0){
                        v[nx][y] = 1;
                         q.push( {{nx,y}, map[nx][y]} ); 
                    }
                }
                nx = x - j;
                if(inRange(nx, y)){
                    if(map[nx][y] != 0 && v[nx][y] == 0){
                        v[nx][y] = 1;
                         q.push( {{nx,y}, map[nx][y]} ); 
                    }
                }
                
                int ny = y + j;
                if(inRange(x, ny)){
                    if(map[x][ny] != 0 && v[x][ny] == 0){
                        v[x][ny] = 1;
                         q.push( {{x,ny}, map[x][ny]} ); 
                    }
                }
                
                ny = y - j;
                if(inRange(x, ny)){
                    if(map[x][ny] != 0 && v[x][ny] == 0){
                        v[x][ny] = 1;
                         q.push( {{x,ny}, map[x][ny]} ); 
                    }
                }
            } // end of for j
        } // end of while
        merge_map();
        return ;
    } // end of for i
}

void dfs(int n){
    if(n == 0){
        int res = cal();
        ans = ans < res ? ans : res;
        return ;
    }
    
    int tmp_map[15][12];
    for(int i=0; i<row; i++) for(int j=0; j<col; j++) tmp_map[i][j] = map[i][j];
    for(int i=0; i<col; i++){
        work(i);
        dfs(n-1);
        for(int i=0; i<row; i++) for(int j=0; j<col; j++) map[i][j] = tmp_map[i][j];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int TC;
    cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        ans = 2e9;
        int n;
        cin >> n >> col >> row;
        for(int i=0; i<row; i++) for(int j=0; j<col; j++) cin >> map[i][j];
        dfs(n);
        cout << "#" << tc << " " << ans << endl ;
    }
    return 0;
}