[JAVA] SWEA 5656 벽돌깨기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

입력

가장 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,
그 다음 줄부터 T 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 N, W, H 가 순서대로 공백을 사이에 두고 주어지고,다음 H 줄에 걸쳐 벽돌들의 정보가 1 줄에 W 개씩 주어진다.

출력

출력은 #t 를 찍고 한 칸 띄운 다음 정답을 출력한다.
(t 는 테스트 케이스의 번호를 의미하며 1 부터 시작한다)

풀이: dfs, bfs

간단한 구현 문제이다. 변수의 제약이 있기 때문에 DFS로 구현하여 풀 수 있다. 벽돌이 깨지는 메커니즘은 BFS로 간단히 구현할 수 있다.

1. 각 열에 대해 구슬을 떨어뜨리는 경우를 dfs방식으로 구현한다.
2. 깨지는 벽돌을 큐에 넣고 방문 처리한다.
3. 큐에서 꺼낸 벽돌의 범위에 따라 새로운 벽돌을 큐에 넣고 방문 처리한다.
4. 중력에 의해 바닥에 붙는 구현도 큐로 구현한다.

코드

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p5656벽돌깨기 {
	static int width, height, N, ans;
	static int[] dx = new int[] {0, 0, 1, -1};
	static int[] dy = new int[] {1, -1, 0, 0};
	static int[][] clone(int [][]grid){
		int[][] res = new int[height][width];
		for(int i=0; i<height; i++) {
			res[i] = grid[i].clone();
		}
		return res;
	}
	static void hit(int posI, int posJ, int[][] grid) {
		Queue<int[]> queue = new LinkedList<int[]>();
		boolean[][] visited = new boolean[height][width];
		queue.offer(new int[] {posI, posJ});
		visited[posI][posJ] = true;
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			if(grid[cur[0]][cur[1]]>1) {
				for(int i=1; i<grid[cur[0]][cur[1]]; i++) {
					for(int j=0; j<4; j++) {
						int ni= cur[0] + i*dy[j];
						int nj = cur[1] + i*dx[j];
						if(0<=ni&&ni<height&&0<=nj&&nj<width&&!visited[ni][nj]) {
							visited[ni][nj]=true;
							queue.offer(new int[] {ni, nj});
						}
					}
				}
			}
			grid[cur[0]][cur[1]] = 0;
		}
	}
	static void gravity(int[][] grid) {
		Queue<Integer> queue = new LinkedList<>();
		for(int j=0; j<width; j++) {
			for(int i=height-1; i>=0; i--) {
				if(grid[i][j] != 0) {
					queue.offer(grid[i][j]);
					grid[i][j] = 0;
				}
			}
			int pos = height-1;
			while(!queue.isEmpty()) {
				grid[pos--][j] = queue.poll();
			}
		}
	}
	static void dfs(int[][] grid, int cnt) {
		if(cnt==N) {
			int count = 0;
			for(int i=0; i<height; i++) {
				for(int j=0; j<width; j++) {
					if(grid[i][j]!=0) {
						count ++;
					}
				}
			}
			ans = Math.min(ans, count);
			return;
		}
		for(int i=0; i<width; i++) {
			int h = height - 1;
			if(grid[height-1][i] != 0) {
				int[][] newgrid = clone(grid);
				while(h >= 0 && grid[h][i] != 0) {
					h--;
				}
				int posI = h+1;
				int posJ = i;
				hit(posI, posJ, newgrid);
				gravity(newgrid);
				dfs(newgrid, cnt+1);
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int testcase = Integer.parseInt(br.readLine());
		for(int t=1; t<=testcase; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			width = Integer.parseInt(st.nextToken());
			height = Integer.parseInt(st.nextToken());
			int[][] grid = new int[height][width];
			for(int i=0; i<height; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<width; j++) {
					grid[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			ans = Integer.MAX_VALUE;
			dfs(grid, 0);
			if(ans == Integer.MAX_VALUE)
				ans = 0;
			System.out.println("#" + t +" "+ans);
			
		}
	}
}