아이디어

• 맵 데이터의 원본을 따로 저장해놓는다.
• 구슬을 N번 명중시킬 N개의 x좌표 쌍의 경우의 수를 모두 탐색한다. (중복순열)
• 순열을 얻었으면, 해당 쌍을 가지고 시뮬레이션을 시작한다.
  • 당연히도 시작 전 맵을 원본 상태로 초기화시켜야 한다.
• 시뮬레이션 과정은 아래의 과정을 N번 반복하면 된다.
  • 해당 x좌표의 열의 가장 윗 줄부터 아래로 탐색하여 처음 등장하는 벽돌을 파괴한다.
    • 해당 타일의 숫자를 0으로 세팅하여 비어있음으로 표시한다.
  • 벽돌이 부서지면 십자 모양으로 (해당 벽돌의 숫자 - 1)칸 만큼 탐색하고, 그 칸이 벽돌이면 재귀적으로 파괴한다.
  • 재귀가 끝났다면, 각 열마다 벽돌이 있는 칸을 아래로 끌어내린다.
• 시뮬레이션이 끝났다면 남아있는 벽돌의 수를 세서, 최솟값을 갱신시킨다. 해당 최솟값이 정답이 된다.

코드

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

public class Solution {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int T, N, W, H, cnt, ans;
    static int[][] mapSrc, map;    // [N][H][W] / N=0: 원본, N=1: 구슬 1번 발사 후, ...
    static int[] tgt;
    
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    
    public static void main(String[] args) throws Exception {
        T = Integer.parseInt(rd.readLine());
        for (int t = 1; t <= T; t++) {
            tk = new StringTokenizer(rd.readLine());
            N = Integer.parseInt(tk.nextToken());
            W = Integer.parseInt(tk.nextToken());
            H = Integer.parseInt(tk.nextToken());

            mapSrc = new int[H][W];
            map = new int[H][W];
            for (int y=0; y<H; y++) {
                tk = new StringTokenizer(rd.readLine());
                for (int x=0; x<W; x++) {
                    mapSrc[y][x] = Integer.parseInt(tk.nextToken());
                }
            }
            
            tgt = new int[N];
            ans = Integer.MAX_VALUE;
            dupperm(0, 0);
            
            sb.append('#').append(t).append(' ').append(ans).append('\n');
        }
        System.out.println(sb);
    }
    
    static void resetMap() {
        for (int y=0; y<H; y++) {
            for (int x=0; x<W; x++) {
                map[y][x] = mapSrc[y][x];
            }
        }
    }

    static void dupperm(int x, int tgtIdx) {
        if (x == W) return;
        if (tgtIdx == N) {
            resetMap();
            simulate();
            ans = Math.min(ans, calcResult());
            return;
        }
        
        tgt[tgtIdx] = x;
        dupperm(0, tgtIdx + 1);
        dupperm(x + 1, tgtIdx);
    }
    
    static void simulate() {
        for (int i=0; i<N; i++) {
            int x = tgt[i];
            int y = 0;
            while (y < H && map[y][x] == 0) y++;
            if (y < H) {
                destroy(y, x);
                pullDown();
            }
        }
    }
    
    static void destroy(int y, int x) {
        if (map[y][x] == 0) return;
        
        int range = map[y][x] - 1;
        map[y][x] = 0;
        
        for (int d=0; d<4; d++) {
            int cy = y;
            int cx = x;
            for (int i=0; i < range; i++) {
                cy += dy[d];
                cx += dx[d];
                if (cy < 0 || cy >= H || cx < 0 || cx >= W) continue;
                destroy(cy, cx);
            }
        }
    }
    
    static void pullDown() {
        for (int x=0; x<W; x++) {
            int y, cy = -1;
            y = H - 1;
            while (y >= 0) {
                if (map[y][x] != 0) {
                    cy = y;
                    while (cy+1 < H && map[cy+1][x] == 0) cy++;
                    if (y < cy) {
                        map[cy][x] = map[y][x];
                        map[y][x] = 0;
                    }
                }
                y--;
            }
        }
    }
    
    static int calcResult() {
        int result = 0;
        for (int x=0; x<W; x++) {
            int y = H - 1;
            while (y >= 0 && map[y][x] != 0) y--;
            result += H - 1 - y;
        }
        return result;
    }
}

리뷰

• 귀찮은 구현문제는 메소드 구분과 플로우를 확실히 하자.