5656 벽돌깨기

 

전략

1. Colum 의 인덱스를 중복이 되도록 N개의 순열을 만들어준다. 

2. 만들어진 순열을 Simulation하여 남은 블록을 센다

3. 그중 최소값을 찾는다.

 

 

인덱스 삽질로 시간을 허비했다.

제출 후, 47번째 TC에서 fail 했으나 유사한 사례를 검색을 통해 찾게 되었다. (참조 사이트)

map을 만들 때, H를 하나 더 증가시켜서 문제 조건의 하나인 맨 윗칸을 비우는 것을 충족시켰다.

 

그런데 왜 맨위가 비었다는 이유로 Pass가 되는지는 아직도 모르겠다.

높이가 H인 경우의 반례를 생각해보려 했으나 코드 동작상 아무런 차이가 없다.

 

import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Solution {

	static int N, H, W;
	static boolean DBG = false;
	static int[][] map, dummy;
	private static int ans;
	static int totalBricks;
	static int dummyTotalBricks;

	public static void main(String args[]) throws Exception {

		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		/*
		File file = new File(
				"C:\\Users\\Lee\\eclipse-workspace\\TestApplication\\src\\com\\test\\testapplication\\output.txt");
		PrintStream ps = new PrintStream(file);
		System.setOut(ps);
		 */

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			totalBricks=0;
			ans = Integer.MAX_VALUE;
			map = new int[H+1][W];
			
			for (int i = 1; i <= H; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] != 0)
						++totalBricks;
				}
			}
			go(0, new int[N]);
			// UnitTest();
			System.out.println("#" + test_case + " " + ans);
		}
	}

	// 중복 순열 : [0,W]사이의 인덱스를 선택하는 경우의 수,
	private static void go(int level,  int[] perm) {
		if (level == N) {
			if (DBG) {
				StringBuilder sb = new StringBuilder();
				for (int v : perm) {
					sb.append(v).append(' ');
				}
				System.out.println(sb);
			}

			dummy = new int[H+1][W];

			for (int i = 0; i <= H; i++) {
				dummy[i] = Arrays.copyOf(map[i], W);
			}

			int rest = simulation(perm);
			ans = Math.min(rest, ans);

		} else {
			for (int i = 0; i < W; i++) {
				perm[level] = i;
				go(level + 1, perm);
			}

		}
	}

	private static void UnitTest() {
		dummy = new int[H+1][W];

		for (int i = 0; i <= H; i++) {
			dummy[i] = Arrays.copyOf(map[i], W);
		}

		int[] perm = new int[3];
		perm[0] = 2;
		perm[1] = 2;
		perm[2] = 6;
		int rest = simulation(perm);
		sort();
		ans = Math.min(rest, ans);

	}

	private static int simulation(int[] perm) {
		dummyTotalBricks = totalBricks;
		for (int i = 0; i < perm.length/* N */ ; i++) {
			int c = perm[i];
			if (DBG)
				System.out.printf("perm[%d] c : %d\n", i, perm[i]);
			for (int r = 0; r <= H; r++) {
				if (dummy[r][c] == 0)
					continue;
				// 스플레시
				int width = dummy[r][c];
				explode(r, c, width);

				if (DBG) {
					System.out.printf("r : %d c: %d width : %d dummyTotalBricks : %d\n", r, c, width, dummyTotalBricks);
					for (int[] ar : dummy) {
						for (int v : ar) {
							System.out.print(v + " ");
						}
						System.out.println();
					}
				}

				sort();
				if (DBG) {
					System.out.println("after sort");
					for (int[] ar : dummy) {
						for (int v : ar) {
							System.out.print(v + " ");
						}
						System.out.println();
					}
				}
				break;
			}
		}
		return dummyTotalBricks;
	}

	private static void sort() {
		// 블록들을 정리한다.
		for (int i = 0; i < W; i++) {
			for (int j = H; j > 1; j--) {
				if (dummy[j][i] == 0) {
					for (int k = j - 1; 0 <= k; k--) {
						if (dummy[k][i] != 0) {
							dummy[j][i] = dummy[k][i];
							dummy[k][i] = 0;
							break;
						}
					}
				}
			}
		}
	}

	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };

	private static void explode(int r, int c, int width) {

		// 현재 터진 자리를 0으로 지운다.
		dummy[r][c] = 0;
		if (DBG)
			System.out.printf("set 0 %d %d %d\n", r, c, dummy[r][c]);
		// 터질 때마다 남은 블록수를 count한다.
		dummyTotalBricks--;

		for (int d = 0; d < 4; d++) {
			for (int w = 1; w < width; w++) {
				// 폭발의 범위내에 터질 블록이 있으면 폭파 시킨다.
				int nr = r + w * dx[d];
				int nc = c + w * dy[d];
				if (nr >= 0 && nr <= H && nc >= 0 && nc < W && dummy[nr][nc] != 0) {
					int nWidth = dummy[nr][nc];
					explode(nr, nc, nWidth);
				}
			}
		}
	}

}

 

 

참조 : https://jongnan.tistory.com/entry/SW-Expert-5656-%EB%B2%BD%EB%8F%8C-%EA%B9%A8%EA%B8%B0