SWEA 5656 [벽돌 깨기]

SW Expert Academy 벽돌 깨기 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

//SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다.

안녕하세요. 이번 문제는 SW Expert Academy의 벽돌 깨기 입니다.

간략하게 설명하자면, 그냥.... 공으로 벽돌 깨기 입니다.

시뮬레이션 부분이 조금 빡셌습니다.

문제 해결방법은 다음과 같습니다.

1. 먼저 공을 어디에 던질지 DFS로 정한다.

2. 해당 공이 영향을 끼치는 부분을, 2차원 배열에 저장하면서 큐에 담는다.

큐를 돌면서, 해당 블록이 영향을 끼치는 부분을 반복적으로 배열에 표시.

3. 표시된 영역의 블록을 지운다.

4. 블록밑이 0이면 떨어트린다.

시뮬레이션 문제는 무작정 많이 풀어봐야 할 것 같습니다...

import java.util.*;
public class Solution {
    public static int T;
    public static int N, W, H;
    public static int Result = 300;
    public static Queue<int[]> q = new LinkedList<int[]>(); 
    public static int[][] d = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    public static boolean boundary(int i, int j) {
        return i >= 0 && i < H && j >= 0 && j < W;
    }
    public static void DFS(int depth, int[][] Map) {
        if(depth == N) {
            int res = 0;
            for(int i = 0; i < H; i++) {
                for(int j = 0; j < W; j++) {
                    if(Map[i][j] != 0)
                        res++;
                }
            }
            Result = Result > res ? res : Result;
            return;
        }
        int[][] temp_map = new int[H][W];
        for(int i = 0; i < H; i++)
            for(int j = 0; j < W; j++)
                temp_map[i][j] = Map[i][j];
        for(int w = 0; w < W; w++) {
            for(int h = 0; h < H; h++) {
                if(Map[h][w] != 0) {
                    int[] block = new int[2];
                    boolean[][] visit = new boolean[H][W];
                    
                    block[0] = h;
                    block[1] = w;
                    visit[block[0]][block[1]] = true;
                    q.offer(block);
                    while(!q.isEmpty()) {
                        int[] arr = q.poll();
                        for(int k = 0; k < 4; k++) {
                            for(int i = 1; i < Map[arr[0]][arr[1]]; i++) {
                                if(boundary(arr[0] + i * d[k][0], arr[1] + i * d[k][1])) {
                                    if(!visit[arr[0] + i * d[k][0]][arr[1] + i * d[k][1]]) {
                                        visit[arr[0] + i * d[k][0]][arr[1] + i * d[k][1]] = true;
                                        int[] node = { arr[0] + i * d[k][0], arr[1] + i * d[k][1] };
                                        q.offer(node);
                                    }
                                }
                            }
                        }
                    }
                    for(int i = 0; i < H; i++) {
                        for(int j = 0; j <W; j++) {
                            if(visit[i][j]) {
                                Map[i][j] = 0;
                            }
                        }
                    }
                    for(int j = 0; j < W; j++) {
                        for(int i = H-1; i >= 0; i--) {
                            if(Map[i][j] == 0) {
                                for(int k = i; k >= 0; k--) {
                                    if(Map[k][j] != 0) {
                                        Map[i][j] = Map[k][j];
                                        Map[k][j] = 0;
                                        break;
                                    }
                                }
                            }
                        }
                    }
                    
                    DFS(depth + 1, Map);
                    for(int i = 0; i < H; i++) 
                        for(int j = 0; j < W; j++)
                            Map[i][j]= temp_map[i][j];
                    break;
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for(int test_case = 1; test_case <= T; test_case++) {
            N = sc.nextInt();
            W = sc.nextInt();
            H = sc.nextInt();
            Result = 300;
            int[][] Map = new int[H][W];
            for(int i = 0; i < H; i++) {
                for(int j = 0; j < W; j++) {
                    Map[i][j] = sc.nextInt();
                }
            }
            DFS(0, Map);
            if(Result == 300)
                Result = 0;
            System.out.println("#" + test_case + " " + Result);
        }
    }
}