[SWEA] 벽돌 깨기

문제

문제 간략화

dfs로 처음 시작( 각각의 세기가 존재 )
파괴하는 메서드를 별도로 분리 필요

풀이

• dfs
  구슬이 몇번째인지와 현재의 배열 상태 입력
  종료 조건 1. 남아있는 것이 없다면 종료
  종료 조건 2. 구슬을 쏠 수 있는 횟수가 더이상 없다면 종료
  -> 이 때 answer로 가장 남아있는 벽돌의 수가 적은 것을 구해주기

    static void dfs(int cnt, int[][] map) {
        int remaining = count(map);
        if (remaining == 0) {
            answer = 0;
            return;
        }
        if (cnt == N) {
            answer = Math.min(answer, remaining);
            return;
        }

        for (int c = 0; c < W; c++) {
            int r = 0;
            while (r < H && map[r][c] == 0) r++;
            if (r == H) continue;

            int[][] copy = new int[H][W];
            for (int i = 0; i < H; i++) {
                System.arraycopy(map[i], 0, copy[i], 0, W);
            }

            explode(r, c, copy);
            down(copy);
            dfs(cnt + 1, copy);

            if (answer == 0) return;
        }
    }

• 폭발에 대한 메서드
  해당 세기만큼 벽돌을 깨는 메서드 분리
  세기만큼 벽돌을 깨는데, 이미 벽돌이 깨져있다면 0이었기에 상관 없음

    static void explode(int r, int c, int[][] map) {
        int power = map[r][c];
        if (power == 0) return;
        map[r][c] = 0;

        if (power == 1) return;

        for (int[] d : dirs) {
            for (int step = 1; step < power; step++) {
                int nr = r + d[0] * step;
                int nc = c + d[1] * step;
                if (nr < 0 || nr >= H || nc < 0 || nc >= W) break;
                if (map[nr][nc] > 0) {
                    explode(nr, nc, map);
                }
            }
        }
    }

• count 메서드

    static int count(int[][] map) {
        int cnt = 0;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                if (map[r][c] > 0) cnt++;
            }
        }
        return cnt;
    }

🤯 주의해야하는 부분

만약 중간이 터진다면 이에 대하여 밑으로 떨어지는 것도 계산해줘야함

    static void down(int[][] map) {
        for (int c = 0; c < W; c++) {
            int write = H - 1;
            for (int r = H - 1; r >= 0; r--) {
                if (map[r][c] > 0) {
                    int val = map[r][c];
                    map[r][c] = 0;
                    map[write][c] = val;
                    write--;
                }
            }
        }
    }

전체 코드

import java.io.*;
import java.util.*;

class Solution {

    static int T, N, W, H;
    static int answer;
    static final int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine().trim());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());

            int[][] board = new int[H][W];
            for (int r = 0; r < H; r++) {
                st = new StringTokenizer(br.readLine());
                for (int c = 0; c < W; c++) {
                    board[r][c] = Integer.parseInt(st.nextToken());
                }
            }

            answer = Integer.MAX_VALUE;
            dfs(0, board);
            System.out.println("#" + tc + " " + answer);
        }
    }

    static void dfs(int cnt, int[][] map) {
        int remaining = count(map);
        if (remaining == 0) {
            answer = 0;
            return;
        }
        if (cnt == N) {
            answer = Math.min(answer, remaining);
            return;
        }

        for (int c = 0; c < W; c++) {
            int r = 0;
            while (r < H && map[r][c] == 0) r++;
            if (r == H) continue;

            int[][] copy = new int[H][W];
            for (int i = 0; i < H; i++) {
                System.arraycopy(map[i], 0, copy[i], 0, W);
            }

            explode(r, c, copy);
            down(copy);
            dfs(cnt + 1, copy);

            if (answer == 0) return;
        }
    }

    static void explode(int r, int c, int[][] map) {
        int power = map[r][c];
        if (power == 0) return;
        map[r][c] = 0;

        if (power == 1) return;

        for (int[] d : dirs) {
            for (int step = 1; step < power; step++) {
                int nr = r + d[0] * step;
                int nc = c + d[1] * step;
                if (nr < 0 || nr >= H || nc < 0 || nc >= W) break;
                if (map[nr][nc] > 0) {
                    explode(nr, nc, map);
                }
            }
        }
    }

    static void down(int[][] map) {
        for (int c = 0; c < W; c++) {
            int write = H - 1;
            for (int r = H - 1; r >= 0; r--) {
                if (map[r][c] > 0) {
                    int val = map[r][c];
                    map[r][c] = 0;
                    map[write][c] = val;
                    write--;
                }
            }
        }
    }

    static int count(int[][] map) {
        int cnt = 0;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                if (map[r][c] > 0) cnt++;
            }
        }
        return cnt;
    }
}