[swexpert] 5656. 벽돌깨기 (java, bfs)

bfs 심화랄까 

 

벽돌을 n번 깨뜨릴 수 있는데 열의 길이 w 중에 어디를 n번 때릴지 미리 결정한 후 (중복조합)

그 다음에 bfs 돌린다고 생각해놓고 짜면 훨씬 낫다.

 

백준 토마토 문제처럼 연속적으로 깨지게 되는 벽돌을 모두 처리한 후 다음 bfs를 돌린다.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y;
	int x;
	int num;
	public Pos(int y, int x, int num) {
		super();
		this.y = y;
		this.x = x;
		this.num = num;
	}
	
}

public class Solution {
	static int t,n,w,h;
	static int[][] map;
	static int[] xpos= {0,0,1,-1};
	static int[] ypos= {1,-1,0,0};
	static ArrayList<Integer> arr=new ArrayList<>();
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			w=sc.nextInt();
			h=sc.nextInt();
			answer=Integer.MAX_VALUE;
			map=new int[h][w];
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					map[i][j]=sc.nextInt();
				}
			}

			// 중복 조합 열길이 wCn 구하기 n번 어디를 칠 건지 미리 구해준다.
			comb(0);
			System.out.printf("#%d %d\n",tc,answer);
			
		}
		
	}
	private static void comb(int cnt) {
		
		if(cnt==n) {
			ball();
			return;
		}
		for (int i = 0; i < w; i++) {
			arr.add(i);
			comb(cnt+1);
			arr.remove(arr.size()-1);
		}
		
	}
	
//	private static void print(int[][] m) {
//		for (int i = 0; i < h; i++) {
//			for (int j = 0; j < w; j++) {
//				System.out.print(m[i][j]+" ");
//			}
//			System.out.println();
//		}
//	}
	
	
	private static void ball() {
		int[][] map2=new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				map2[i][j]=map[i][j];
			}
		}
		
		//n번 만큼 터트림
		for (int c = 0; c < n; c++) {
			int col=arr.get(c); //터트리는 열
			for (int i = 0; i <h ; i++) {//터트릴 수 있으면 터트림. 0인 곳없으면 다시 탐색
				if(map2[i][col]!=0) {//터트릴 수 있다. 터트린 후 break
					Queue<Pos> q=new LinkedList<Pos>();
					q.add(new Pos(i,col,map2[i][col]-1));
					map2[i][col]=0;
					
					while(q.size()!=0) {
						int size=q.size();
						for (int l = 0; l < size; l++) {
							Pos cur=q.poll();
							int y=cur.y;
							int x=cur.x;
							int num=cur.num;
							
							for (int k = 0; k < 4; k++) {
								for (int p = 1; p <=num; p++) {
									int yy=y+ypos[k]*p;//터트리는 길이
									int xx=x+xpos[k]*p;
									if(xx<0 || yy<0 || xx>=w ||yy>=h)continue;
									if(map2[yy][xx]==0)continue;
									q.add(new Pos(yy,xx,map2[yy][xx]-1));
									map2[yy][xx]=0;	
								}
							}
							

						}
						
						
					}
					//이거 하나때문에 디버깅한참함 ^^... 해당 열에서 0아닌 곳터트린 후 break
					break;
				}
		}
			
			//터트린 다음 떨어뜨리기
			for (int j = 0; j < w; j++) {
				for (int r = h-1; r >=0; r--) {
					if(map2[r][j]==0) {//0인곳 있으면 0이 아닌 가장 가까운 곳 가서 끌어내림
						for (int r2 = r-1; r2 >=0; r2--) {
							if(map2[r2][j]!=0) {
								map2[r][j]=map2[r2][j];
								map2[r2][j]=0;
								break;
							}
						}
					}
					//아직도 0이면 더이상 내릴 것 없다는 뜻
					if(map2[r][j]==0) {
						break;
					}
				}
			}

		
		}

			//n번 터트리고 남은 벽돌 계산
			int sum=0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if(map2[i][j]!=0)sum+=1;
				}
			}
			if(answer>sum)answer=sum;

	}

}