swea-5656.md

---
layout    : wiki
title     : SWEA 5656. 벽돌 깨기
summary   : 
date      : 2021-04-14 13:50:14 +0900
updated   : 2021-12-15 18:29:18 +0900
tag       : simulation
public    : true
published : true
parent    : [[swea]]
latex     : false
---
* TOC
{:toc}


- 모든 경우의 수를 탐색하면서 최대로 제거할 수 있는 경우를 찾는다.
- 떨어뜨릴 수 있는 구슬 수만큼 재귀 함수를 수행한다.
- 제거되어야 할 벽돌의 위치를 queue에 넣어 이후에 해당 벽돌로 인해 제거되어야 할 벽돌들을 탐색한다.


```java linenos
import java.io.*;
import java.util.*;

public class Solution {
	static int N, M, X, res;
	static int[][] board;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = {  0,-1, 0, 1 };

	static void copy(int[][] src, int[][] dest) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				dest[i][j] = src[i][j];
	}

	static int countRemain() {
		int cnt = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (board[i][j] != 0) cnt++;

		return cnt;
	}

	static void go(int cnt) {
		if (cnt >= X) {
			res = Math.min(res, countRemain());
			return;
		}

		int[][] backupBoard = new int[N][M];
		copy(board, backupBoard);

		for (int i = 0; i < M; i++) {
			drop(i);

			go(cnt+1);
			copy(backupBoard, board);
		}
	}

	static void drop(int sc) {
		int sr = 0;
		// 제일 상위에 있는 벽돌 탐색
		while (sr < N && board[sr][sc] == 0) sr++;
		if (sr >= N) return;

		Queue<Integer> q = new ArrayDeque<>();
		q.offer(sr); q.offer(sc);

		while (!q.isEmpty()) {
			int r = q.poll();
			int c = q.poll();

			// 해당 벽돌로 인해 제거할 벽돌의 범위 설정
			int range = board[r][c];
			// 0으로 설정하여 방문한 위치임을 나타낸다
			board[r][c] = 0;
			for (int i = 0; i < 4; i++) {
				int nr = r, nc = c;
				for (int j = 1; j < range; j++) {
					nr += dx[i];
					nc += dy[i];
					// 범위를 벗어나면 더 이상 갈 필요없다
					if (nr < 0 || nr >= N || nc < 0 || nc >= M)
						break;
					// 0이라면 원래 벽돌이 없었거나, 이미 벽돌이 제거된 위치이다
					if (board[nr][nc] == 0) continue;

					q.offer(nr); q.offer(nc);
				}
			}
		}

		// 제거 대상 벽돌 제거 및 재정렬
		for (int j = 0; j < M; j++) {
			Queue<Integer> tmpq = new ArrayDeque<>();
			for (int i = N-1; i >= 0; i--) {
				if (board[i][j] == 0) continue;
				tmpq.offer(board[i][j]);
				board[i][j] = 0;
			}
			int i = N-1;
			while (!tmpq.isEmpty()) board[i--][j] = tmpq.poll();
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int testcase = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= testcase; tc++) {
			res = Integer.MAX_VALUE;
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			X = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());

			board = new int[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < M; j++)
					board[i][j] = Integer.parseInt(st.nextToken());
			}
			go(0);
			System.out.println("#" + tc + " " + res);
		}
	}
}
```