SWEA 5656 - 벽돌 깨기

Java

5656 번 - 벽돌 깨기

문제

N 개의 벽돌을 떨어트려 최대한 많은 벽돌을 제거하려고 한다.
N, W, H, 그리고 벽돌들의 정보가 주어질 때,
▶ 남은 벽돌의 개수를 구하라!

접근 방법

board의 가로 길이가 최대 12이고 구슬의 개수는 최대 4개이다.
따라서 0부터 W-1까지 구슬을 하나씩 다 떨어뜨려 보면서, 각 경우마다 남은 벽돌의 개수 중 제일 적은 값을 도출해낸다.
따라서, 떨어뜨릴 구슬의 위치를 정하는 총 경우의 수는 12^4가 된다.
이는 DFS을 통하여 중복순열을 사용한 것이다.

위치를 정한 뒤, 구슬을 떨어뜨려 벽돌을 깬다.
Queue를 사용하여 벽돌 하나를 깻을 때 연쇄적으로 깨지는 벽돌도 저장한다.
이후 Queue에서 다음 연쇄 깨질 벽돌을 꺼내여 다시 범위대로 퍼뜨려 본다.
즉 BFS와 비슷한 방식으로 이용한다.

한번 벽돌을 떨어뜨리고 연쇄 반응으로 벽돌을 제거하였다면, 공중에 벽돌에 떠있다.
따라서 공중에 떠있는 벽돌을 아래로 내려야한다.
각 열마다 탐색하여, deque에 벽돌을 저장하고 아래서부터 하나씩 꺼내어 아래로 몰아 넣는다.

코드

import java.io.*;
import java.util.*;

class Solution {
	static int result = 0, bCnt, n, m;
	static int[][] saved, map;
	static int[] sel;
	public static void main(String []args) throws Exception {  
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	int tc = stoi(br.readLine());
    	
    	for(int tidx = 1; tidx <= tc; tidx++) {
    		result = Integer.MAX_VALUE;
    		stk = new StringTokenizer(br.readLine()); 
    		
    		bCnt = stoi(stk.nextToken());
    		m = stoi(stk.nextToken());
    		n = stoi(stk.nextToken());
    		
    		map = new int[n][m];
    		saved = new int[n][m];
    		sel = new int[bCnt];
    		
    		for(int i = 0; i < n; i++) {
    			stk = new StringTokenizer(br.readLine());
    			for(int j = 0; j < m; j++) {
    				map[i][j] = stoi(stk.nextToken());
    				saved[i][j] = map[i][j];
    			}
    		}
    		// ------- 초기화 끝 ----------
    		
    		DFS(0);
    		
    		System.out.println("#" + tidx + " " + result);
    	}
    	
	}
	// n개의 떨어뜨릴 구슬의 위치를 정하는 DFS
	static void DFS(int lv) {
		if(lv == bCnt) {
			init();		// 초기 상태로 되돌린다.
			result = Math.min(result, cal());
			return;
		}
		for(int i = 0; i < m; i++) {
			sel[lv] = i;
			DFS(lv + 1);
		}
	}
	
	static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};
	
	private static int cal() {
		
		int curX, curY = 0, y, x, ny, nx, range;
		int[] temp;
		Queue<int[]> queue = new LinkedList<int[]>();
		for(int idx = 0; idx < bCnt; idx++) {
			curX = sel[idx];
			curY = 0;
			// 처음 터질 벽돌의 위치를 찾는다.
			while(true) {
				if(!isIn(curY,curX) || map[curY][curX] != 0)
					break;
				curY++;
			}
			if(!isIn(curY,curX)) continue;
			
			queue.add(new int[] {curY, curX});
			
			// 벽돌 하나를 깨트리고, 그에 따른 연쇄 벽돌도 다 깨뜨린다.
			while(!queue.isEmpty()) {
				temp = queue.poll();
				y = temp[0];
				x = temp[1];
				range = map[y][x] - 1;
				map[y][x] = 0;
				
				// 4방향으로 범위 만큼 연쇄하여 터뜨린다
				for(int i = 0; i < 4; i++) {
					ny = y;
					nx = x;
					for(int j = 0; j < range; j++) {
						ny += dy[i];
						nx += dx[i];
						if(isIn(ny,nx) && map[ny][nx] != 0) {
							queue.add(new int[] {ny,nx});
						}
					}
				}
			}
			
			// 공중에 떠있는 벽돌을 다 내린다
			Deque<Integer> above = new ArrayDeque<>();
			for(int j = 0; j < m; j++) {
				for(int i = 0; i < n; i++) {
					if(map[i][j] != 0) {
						above.add(map[i][j]);
					}
					map[i][j] = 0;
				}
				int index = n - 1;
				while(!above.isEmpty()) {
					map[index--][j] = above.pollLast();
				}
			}
		}
		
		// 남아있는 벽돌의 개수를 센다
		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;
	}

	public static void init() {
		for(int i = 0; i < n; i++) {
			map[i] = saved[i].clone();
		}
	}
	
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

굳굳

개선할 점

없