SWEA 5656 벽돌 깨기(JAVA) 🔨

구조화

• 중복 순열로 몇번째 열에서 벽돌 깨기를 할 지 경우의 수 구하기
• N번 (각 열마다 돌려서 가장 벽돌을 많이 깨는 열 구하기) 반복
• 벽돌을 깼으면 중력 작용

소스 코드

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

public class Solution_5656_벽돌깨기 {

	// T: 테스트케이스 횟수
	// N: 벽돌 깨기 반복횟수, W: 열, H: 행
	static int T, N, W, H, result;
	static int[][] map, copy;

	static int[] pick;
	// 상하좌우
	static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	static boolean[][] visited;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());

			result = Integer.MAX_VALUE;
			pick = new int[N];
			map = new int[H][W];
			copy = new int[H][W];
			visited = new boolean[H][W];

			for (int h = 0; h < H; h++) {
				st = new StringTokenizer(br.readLine());
				for (int w = 0; w < W; w++) {
					map[h][w] = Integer.parseInt(st.nextToken());
				}
			}

			// 중복 순열
			perm(0);
			System.out.printf("#%d %d%n", t, result);
		}
	}

	private static void perm(int cnt) {

		if (cnt == N) {
			for (int h = 0; h < H; h++) {
				copy[h] = map[h].clone();
			}

			for (int i = 0; i < N; i++) {
				bfs(pick[i]);
			}

			// 남은 벽돌 갯수 카운트
			int cntBrick = count();
			if (result > cntBrick)
				result = cntBrick;
			return;
		}

		for (int i = 0; i < W; i++) {
			pick[cnt] = i;
			perm(cnt + 1);
		}
	}

	private static int count() {

		int cnt = 0;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
				if (copy[h][w] != 0)
					cnt++;
			}
		}
		return cnt;
	}

	// 벽돌 깨기
	private static void bfs(int start) {
		Queue<int[]> q = new LinkedList<int[]>();
		for (int h = 0; h < H; h++) {
			// 0이 아닌 경우
			if (copy[h][start] != 0) {
				q.offer(new int[] { h, start });
				visited[h][start] = true;
				break;
			}
		}

		while (!q.isEmpty()) {

			int[] cur = q.poll();
			int cx = cur[0];
			int cy = cur[1];
			int loop = copy[cx][cy] - 1;

			// 가운데 값 처리
			copy[cx][cy] = 0;
			// 맵의 수 -1 만큼 반복
			for (int i = 1; i <= loop; i++) {
				// 델타
				for (int w = 0; w < 4; w++) {
					int nx = cx + (way[w][0] * i);
					int ny = cy + (way[w][1] * i);

					if (isRight(nx, ny) && copy[nx][ny] > 0) {
						q.offer(new int[] { nx, ny });
					}
				}
			}

		}
		copy = gravity(copy);

	}

	// 중력 작용
	private static int[][] gravity(int[][] copyMap) {

		Queue<int[]> q = new LinkedList<int[]>();

		// 0이 아닌거 찾기
		for (int w = 0; w < W; w++) {
			for (int h = H - 1; h >= 0; h--) {
				if (copyMap[h][w] != 0) {
					q.offer(new int[] { copyMap[h][w], w });
					copyMap[h][w] = 0;
				}
			}
		}
		int col = -1;
		int h = H - 1;
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int val = cur[0];

			if (col != cur[1])
				h = H - 1;
			col = cur[1];
			// for (int h = H-1; h >= 0; h--)
			{
				copyMap[h--][col] = val;
			}
		}
		return copyMap;
	}

	// 경계 체크
	private static boolean isRight(int nx, int ny) {

		if (nx >= 0 && nx < H && ny >= 0 && ny < W)
			return true;
		return false;
	}

}