[SWEA] 5656. 벽돌 깨기

 

주어진 구슬 N의 최대 크기가 4, 너비 W가 12이므로 모든 경우의 수를 구할 때 순열을 사용하여도 복잡도가 넘어 갈 것 같지 않아서 바로 순열을 사용하였다.

순열을 선택한 후 다음과 같은 과정을 계획하였다.
1. W에서 N개를 선택하는 모든 수열을 구한다.
2-1. 구한 순열의 경우의 수마다 위에서 부터 폭파하는 과정을 BFS를 통하여 계산한다.
2-2. 폭파된 후 중간에 공백을 아래로 당겨준다. 그 후 2-1 반복한다.
3. 모든 폭파가 종료된 후 살아있는 블럭을 카운팅해준다.
또한, 중간에 최적화를 시키기 위해, 만일 2-1 과정에서 선택한 열의 블록이 하나도 없는 경우, 그 순열의 경우는 바로 종료 시키게 해주었다.

문제를 읽고 있는 그대로 차분하게 구현하여서 답을 얻을 수 있었다.

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution_5656_벽돌깨기  {
 
    static int row,col;
    static int r;
    static int[][] mapOrigin;
    static int[][] map;
    
    static int[] data;
    static int[] pick;
    
    static int result;
    static boolean finish;
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j,num;
        public Pos(int i,int j,int n) {
            this.i=i;this.j=j;num=n;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=1;tc<=T;tc++) {
            st=new StringTokenizer(br.readLine());
            r=Integer.parseInt(st.nextToken());
            col=Integer.parseInt(st.nextToken());
            row=Integer.parseInt(st.nextToken());
 
            mapOrigin=new int[row][col];
            map=new int[row][col];
            for(int i=0;i<row;i++) {
                st=new StringTokenizer(br.readLine());
                for(int j=0;j<col;j++)
                    mapOrigin[i][j]=Integer.parseInt(st.nextToken());
            }
            
            data=new int[col];
            for(int i=0;i<col;i++)
                data[i]=i;
            
            pick=new int[r];
            queue= new LinkedList<>();
            result=Integer.MAX_VALUE;
            perm(0,0);
            
            if(result==Integer.MAX_VALUE)
                result=0;
            System.out.println("#"+tc+" " +result);
        }
        
    }
    
    static void perm(int start, int depth) {
        if(depth==r) {
//            System.out.println(Arrays.toString(pick));
            //배열 복사
            for(int i=0;i<row;i++) {
                for(int j=0;j<col;j++)
                    map[i][j]=mapOrigin[i][j];
            }
            
            //1. pick을 이용하여 벽돌깨기
            finish=false;
            
            breakWall();
            
            if(finish)
                return;
            
            
            
            //3.카운팅
            int count=0;
            for(int i=0;i<row;i++) {
                for(int j=0;j<col;j++) {
                    if(map[i][j]>0)
                        count++;
                }
            }
            result=Math.min(result, count);
            
            return;
        }
        for(int i=0;i<col;i++) {
            pick[depth]=data[i];
            perm(i,depth+1);
        }
    }
    
    static void breakWall() {
        //1. pick을 이용하여 벽돌깨기
        for(int i=0;i<r;i++) {
            int index =pick[i];
            int stop=-1;
            for(int ii=0;ii<row;ii++) {
                if(map[ii][index]!=0) {
                    stop=ii;
                    break;
                }
            }
            
            if(stop==-1) {
                finish=true;
                return;
            }
            
            queue.offer(new Pos(stop, index, map[stop][index]));
            map[stop][index]=0;
            while(!queue.isEmpty()) {
                Pos cur =queue.poll();
//                map[cur.i][cur.j]=0;
//                System.out.println(cur.i+","+cur.j);
                int dis = cur.num;
                
                if(dis!=1) {
                    for(int dir=0;dir<4;dir++) {
                        for(int len=1;len<dis;len++) {
                            int nextI = cur.i+di[dir]*len;
                            int nextJ = cur.j+dj[dir]*len;
                            
                            if(nextI>=0 && nextI<row && nextJ>=0 && nextJ<col) {
                                if(map[nextI][nextJ]==1) {
                                    map[nextI][nextJ]=0;
                                }else if(map[nextI][nextJ]>1) {
                                    queue.offer(new Pos(nextI, nextJ, map[nextI][nextJ]));
                                    map[nextI][nextJ]=0;
                                }
                            }
                        }
                        
                    }
                }
            }
            
            //2.중간에 0나오는 것 땅기기
            for(int cc=0;cc<col;cc++) {
                for(int rr=row-1;rr>=0;rr--) {
                        if(map[rr][cc]==0) {
                            for(int k=rr-1;k>=0;k--) {
                                if(map[k][cc]!=0) {
                                    map[rr][cc]=map[k][cc];
                                    map[k][cc]=0;
                                    break;
                                }
                            }
                        }
                }
            }
        }
    }
}