SEA5656_벽돌깨기

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

문제정리

1. 구슬은 N번만 쏠 수 있다 , W = C , H = R 이다

2. 0은 빈 공간 , 그 외의 숫자는 벽돌을 의미한다 1~9

3. 구슬은 좌, 우로만 움직일 수 있어서 항상 맨 위에 있는 벽돌만 깨트릴 수 있다

4. 구슬이 명중한 벽돌의 상하좌우로 (벽돌에 적힌 숫자 - 1)칸 만큼 같이 제거된다

5. 제거되는 범위 내에 있는 벽돌은 동시에 제거된다

6. 빈 공간이 잇을 경우 벽돌은 밑으로 떨어지게 된다

7. N개의 구슬을 떨어트려 최대한 많은 벽돌을 제거하려고 한다

8. 최대한 많은 벽돌을 제거하는 경우일때 남은 벽돌의 개수를 출력

9. 1 <= N <= 4 , 2 <= W <= 12 , 2 <= H <= 15

문제 issue

1. map_clone 사용을 습관화 해야한다

2. 떨어지는 부분 구현에서 q2에 있는 데이터를 밑에서 부터 넣기만 하면 끝난다고 생각했지만 인덱스 map.length - q2_size - 1부터 0까지는

0으로 만들어 줘야한다

3. q에 add할때 0은 넣을 필요 없기 때문에 > 1을 추가 해주니 시간초과를 해결하였다

해결흐름

1. 크기가 N인 배열 생성 , 그 안에 0~W-1 중에서 어디에 떨어트릴 것인가를 설정해준다

2. wHn 중복조합으로 풀면됨 , 조합 한개마다 solve로 가기전에 map_clone에 map을 복사해준다

solve에서는 map_clone만 사용한다

3. 떨어지는 위치에서 처음으로 만나는 벽돌을 q에 담아준다 , 네 방향으로 벽의 크기-1 만큼보면서 크기가 1 이상일 경우만

q에 add해준다 , 동시에 0으로 만들어 준다

4. 떨어지는 부분 -> 열을 고정하고 밑에서 부터 위로 가면서 0이 아닌부분을 q에 담고

다시 밑에서 부터 넣어준다 , map.length - q2_size - 1부터는 원래 있던 데이터이기 때문에 0으로 만들어준다

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
 
    private static int N;
    private static int W;
    private static int H;
    private static int min;
    private static int stone_cnt;
    private static LinkedList<stone> q;
    private static int[] temp;
    private static int[] arr;
    private static int[][] map;
    private static int[][] map_clone;
    private static int[] dr = { -1, 0, 1, 0 };
    private static int[] dc = { 0, 1, 0, -1 };
 
    static class stone {
        int r;
        int c;
        int number;
 
        public stone(int r, int c, int number) {
            super();
            this.r = r;
            this.c = c;
            this.number = number;
        }
    }
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int t = 1; t <= test_case; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            map = new int[H][W];
            map_clone = new int[H][W];
            temp = new int[N];
            arr = new int[W];
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine().trim(), " ");
                for (int j = 0; j < W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            for (int i = 0; i < W; i++) {
                arr[i] = i;
            }
 
            // start
            q = new LinkedList<stone>();
            min = Integer.MAX_VALUE;
            nHr(0, 0);
            System.out.println("#" + t + " " + min);
        } // end of test_case
    } // end of main
 
    private static void nHr(int len, int t) {
        if (len == N) {
            // temp배열이용 , 벽 깨고 남은 벽 최솟값 갱신
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    map_clone[i][j] = map[i][j];
                }
            }
            solve();
            if (min > stone_cnt)
                min = stone_cnt;
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            temp[len] = arr[i];
            nHr(len + 1, i);
        }
    }
 
    private static void solve() {
        for (int i = 0; i < temp.length; i++) {
 
            // 벽돌깨고
            int temp_c = temp[i];
            for (int rr = 0; rr < H; rr++) {
                // 가장 위에 있는 벽돌 찾아
                if (map_clone[rr][temp_c] != 0) {
                    q.add(new stone(rr, temp_c, map_clone[rr][temp_c]));
                    break;
                }
            }
            while (!q.isEmpty()) {
                stone s = q.poll();
                int r = s.r;
                int c = s.c;
                int number = s.number;
                map_clone[r][c] = 0;
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < number - 1; k++) {
                        int nr = r + dr[j];
                        int nc = c + dc[j];
                        if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                            if(map_clone[nr][nc] > 0) {
                                q.add(new stone(nr, nc, map_clone[nr][nc]));
                            }
                            map_clone[nr][nc] = 0;
                            r = nr;
                            c = nc;
                        }
                    }
                    r = s.r;
                    c = s.c;
                }
            }
            // 아래로 내리고
            Queue<Integer> q2 = new LinkedList<>();
            for (int j = 0; j < W; j++) {
                for (int k = H - 1; k >= 0; k--) {
                    if (map_clone[k][j] != 0) {
                        q2.add(map_clone[k][j]);
                    }
                }
                int r_idx = H - 1;
                int q2_size = q2.size();
                while (!q2.isEmpty()) {
                    map_clone[r_idx--][j] = q2.poll();
                }
                for (int k = map_clone.length - q2_size-1; k >=0; k--) {
                    map_clone[k][j] = 0;
                }
            }
        }
        // 남은 벽돌 개수 파악
        stone_cnt = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (map_clone[i][j] != 0) {
                    stone_cnt++;
                }
            }
        }
    } // end of solve
} // end of class