SWEA_벽돌깨기_5656

1. 과정

- 최대 4번 떨어뜨릴 수 있고, width가 가장 긴 경우 12이므로 최악의 경우 4의 12승, 2의 24승으로 170만이 조금 안된다. 그냥 완탐해도 된다.

- bfs로 터뜨리면서 연쇄폭발되는 모든 칸을 지워줌

- 그리고 모두 drop시킴

 

 

2. 구현

언어 : JAVA

메모리 : 110,924 kb

실행시간 : 1,119 ms

import java.util.*;

public class SWEA_벽돌깨기_5656 {

	static int N, R, C, answer, total;
	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	static int[][] map;
	
	static class Brick{
		int r, c, num;

		public Brick(int r, int c, int num) {
			this.r = r;
			this.c = c;
			this.num = num;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int testCase = 1; testCase <= T; ++testCase) {
			N = sc.nextInt();
			C = sc.nextInt();
			R = sc.nextInt();
			map = new int[R][C];
			answer = Integer.MAX_VALUE;
			total = 0;
			for(int i=0; i<R; ++i) {
				for(int j=0; j<C; ++j) {
					map[i][j] = sc.nextInt();
					if(map[i][j]>0)
						total++;
				}
			}
			ArrayList<Integer> list = new ArrayList<Integer>();
			go(list);
			System.out.println("#"+testCase+" "+answer);
		}

	}

	private static void go(ArrayList<Integer> list) {
		if(list.size()==N) {
			solve(list);
			return;
		}
		
		for(int i=0; i<C; ++i) {
			list.add(i);
			go(list);
			list.remove(list.size()-1);
		}
	}

	private static void solve(ArrayList<Integer> list) {
		int[][] tmap = getMap();
		int cnt = 0;
		for(int i=0; i<N; ++i) {
			cnt += bomb(tmap, list.get(i));
			drop(tmap);
		}
		answer = Math.min(answer, total-cnt);		
	}

	// bfs로 연쇄폭파 시키고, 폭파된 벽돌 개수 반환
	private static int bomb(int[][] tmap, int col) {
		int cnt = 0;
		for(int i=0; i<R; ++i) {
			if(tmap[i][col]>0) {
				Queue<Brick> q = new LinkedList<Brick>();
				q.add(new Brick(i, col, tmap[i][col]));
				cnt++;
				tmap[i][col] = 0;
				while(!q.isEmpty()){
					Brick brick = q.poll();
					int r = brick.r;
					int c = brick.c;
					int num = brick.num-1;
					for(int j=0; j<4; ++j) {
						int tr = r;
						int tc = c;
						for(int k=0; k<num; ++k) {
							tr += dr[j];
							tc += dc[j];
							if(tr<0 || tc<0 || tr>=R || tc>=C)
								break;
							if(tmap[tr][tc]==0) continue;
							q.add(new Brick(tr, tc, tmap[tr][tc]));
							tmap[tr][tc] = 0;
							cnt++;
						}
					}
				}				
				break;
			}
		}
		return cnt;
	}

	// 벽돌을 떨어뜨리는 메소드
	private static void drop(int[][] tmap) {
		Queue<Integer> q = new LinkedList<Integer>();
		for(int i=0; i<C; ++i) {
			q.clear();
			for(int j=R-1; j>=0; --j) {
				if(tmap[j][i]==0) continue;
				q.add(tmap[j][i]);
				tmap[j][i] = 0;
			}
			int idx = R-1;
			while(!q.isEmpty()) {
				tmap[idx--][i] = q.poll();
			}
		}
	}
	
	// 매번 다른 위치에서 떨어뜨리기위해 map을 갱신함
	private static int[][] getMap() {
		int[][] tmap = new int[R][C];
		for(int i=0; i<R; ++i) {
			for(int j=0; j<C; ++j) {
				tmap[i][j] = map[i][j];
			}
		}
		return tmap;
	}

}