[SWEA 5656번] 벽돌 깨기 :: 늦깎이 IT

[SWEA 5656번 벽돌 깨기 URL]

[풀이 방법]

1. 공을 떨어뜨릴 자리를 찾는다. 만약 검사하는 열에 블럭이 하나도 없을 경우에는 공을 떨어뜨리지 않는다.

 - dropBall() 메소드를 보면, 어느 임의의 열에 대한 행을 모두 검사한다. 모든 행에 블럭이 없을 경우에는 false를 리턴한다. 

 - 행에 블럭이 하나라도 있으면, 공을 떨어뜨린다. 맨 처음 공이 닿는 블럭으로부터 BFS 탐색을 시작하면서

범위안에 있는 블럭들을 Queue에 담아주면서 탐색을 진행한다.

2. 공을 떨어뜨리고, 게임을 1회 진행했으면 모든 블럭들을 바닥으로 떨어뜨린다. dropBlock() 메소드 참조.

3. 만약에, 모든 열에 대해서 dropBall() 메소드가 false를 리턴했다면 그것은 이미 모든 블럭이 사라졌다는

뜻이므로 ans에 0을 넣어준다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int tCase, N, W, H, ans;
    static int[][] map;
    static boolean[] visited;
    static int[] dirX = new int[] { 0, 0, 1, -1 };
    static int[] dirY = new int[] { 1, -1, 0, 0 };
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
 
            map = new int[H][W];
            ans = Integer.MAX_VALUE;
 
            for (int i = 0; i < H; i++) {
 
                st = new StringTokenizer(br.readLine());
 
                for (int j = 0; j < W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            dfs(0, map);
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void dfs(int depth, int[][] prev) {
 
        if (ans == 0)
            return;
 
        if (depth == N) {
            int cnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (prev[i][j] != 0)
                        cnt += 1;
                }
            }
            ans = Math.min(ans, cnt);
            return;
        }
 
        boolean already = true;
        for (int i = 0; i < W; i++) {
 
            int[][] temp = new int[H][W];
            for (int j = 0; j < H; j++)
                temp[j] = Arrays.copyOf(prev[j], prev[j].length);
 
            if (dropBall(temp, i)) {
                dropBlock(temp);
                dfs(depth + 1, temp);
                already = false;
            }
        }
        if (already)
            ans = 0;
    }
 
    public static void dropBlock(int[][] prev) {
 
        for (int i = 0; i < W; i++) {
 
            for (int j = H - 1; j > 0; j--) {
 
                if (prev[j][i] == 0) {
 
                    for (int k = j - 1; k >= 0; k--) {
                        if (prev[k][i] != 0) {
                            prev[j][i] = prev[k][i];
                            prev[k][i] = 0;
                            break;
                        }
                    }
                }
            }
        }
    }
 
    public static boolean dropBall(int[][] prev, int curCol) {
 
        int curRow = -1;
        for (int i = 0; i < H; i++) {
            if (prev[i][curCol] != 0) {
                curRow = i;
                break;
            }
        }
        if (curRow == -1)
            return false;
 
        boolean[][] visited = new boolean[H][W];
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(curRow, curCol, prev[curRow][curCol]));
        prev[curRow][curCol] = 0;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int cnt = node.cnt;
 
            for (int i = 0; i < 4; i++) {
 
                int nr = node.row;
                int nc = node.col;
 
                for (int j = 0; j < cnt - 1; j++) {
 
                    nr += dirX[i];
                    nc += dirY[i];
 
                    if (!isBoundary(nr, nc))
                        break;
 
                    if (prev[nr][nc] != 0) {
                        q.offer(new Node(nr, nc, prev[nr][nc]));
                        prev[nr][nc] = 0;
                    }
                }
            }
        }
        return true;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < H) && (col >= 0 && col < W);
    }
 
    public static void showMap(int[][] prev) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}
 
class Node {
 
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int num) {
        this.row = row;
        this.col = col;
        this.cnt = num;
    }
 
}