[시뮬레이션]벽돌 깨기(SWEA 5656번, 자바)☆☆☆

 

구현 - 시뮬레이션

 

1. 구슬 떨어뜨리기

-> 중복 순열 

2. 구슬이 떨어지는 첫 벽돌 찾기 

3. 첫 벽돌 기준 4방으로 폭발 

4. 벽돌 깨기 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Solution_5656_벽돌깨기{

	static int[][] move= {{1,0},{0,1},{0,-1},{-1,0}};
	
	static int N, H,W;
	static int[][] map;
	static int[][] map2;
	static int answer;
	static int[] num;

	public static void main(String[] args) throws IOException {
		 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 int T = Integer.parseInt(br.readLine());
		 StringTokenizer st;
		 
		 for(int t_c=1;t_c<=T;t_c++) {
			
			 answer=Integer.MAX_VALUE;
			 
			 st=new StringTokenizer(br.readLine());
			 N=Integer.parseInt(st.nextToken());
			 W=Integer.parseInt(st.nextToken());
			 H=Integer.parseInt(st.nextToken());
			
			 map=new int[H][W];
			 for(int i=0;i<H;i++) {
				 st=new StringTokenizer(br.readLine());
				 for(int j=0;j<W;j++) {
					 map[i][j]=Integer.parseInt(st.nextToken());
				 }
			 }
			
			 num=new int[N];
			
			 
			 putMarble(0);
			 System.out.println("#"+t_c+" "+answer);
		 }		
	}
	
	static void putMarble(int cnt) {
		
		if(cnt>=N) {
			map2=new int[H][W];
			for(int i=0;i<H;i++) map2[i]=map[i].clone();
			for(int i=0;i<N;i++) {
				for(int j=0;j<H;j++) {
					if(map2[j][num[i]]>0) {
						breakBricks(j, num[i], map2[j][num[i]]);
						break;
					}
				}moveBricks();
				
			}		
			answer=Math.min(answer, countBricks());
			return;
		}
		for(int i=0;i<W;i++) {
			num[cnt]=i;
			putMarvel(cnt+1);
			
		}
	}
	static int killCnt=0;
	
	static void breakBricks(int x, int y, int size) {
		
		map2[x][y]=0;
		
		for(int i=0;i<4;i++) {
			int nx=x;
			int ny=y;
			for(int j=0;j<size-1;j++) {
				nx=nx+move[i][0];
				ny=ny+move[i][1];
				if(nx<0 || nx>=H || ny<0 || ny>=W) break;
				if(map2[nx][ny]>0) { 
					breakBricks(nx,ny,map2[nx][ny]);
				}
			}
			
		}

	}
	
	
	static int countBricks() {
		int countBricks=0;
		for(int i=0;i<W;i++) {
			for(int j=0;j<H;j++) {
				if(map2[j][i]>0) countBricks++; 
			}
		}
		return countBricks;
	}
	
	static void moveBricks() {
		Stack<Integer> stack=new Stack<>();
		 for(int i=0;i<W;i++) {
			 for(int j=0;j<H;j++) {
				 if(map2[j][i]>0) {
					 stack.push(map2[j][i]);
					 map2[j][i]=0;
				 }
			 }
			int c=H-1;
			while(!stack.isEmpty()) {
				map2[c--][i]=stack.pop();
			}
		 }
	}
	
	
}