[5656] [모의 SW 역량테스트] 벽돌 깨기

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&problemTitle=5656&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

 

문제 해결 방법

중복순열과 bfs를 사용하여 구현했다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {
    static int N, W, H, max, allCnt;
    static int[][] map, copy;
    static int[] colArr;
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 1; t <= T; t++) {
            N = sc.nextInt();
            W = sc.nextInt();
            H = sc.nextInt();
            map = new int[H][W];
            colArr = new int[N];
            max = 0;
            allCnt = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    map[i][j] = sc.nextInt();
                    if (map[i][j] > 0) allCnt++;
                }
            }
            getCol(0);
            System.out.println("#" + t + " " + (allCnt - max));
        }
    }

    private static void getCol(int cnt) {
        if (cnt == N) {
            copy = new int[H][W];
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    copy[i][j] = map[i][j];
                }
            }
            int n = shoot();

            max = Math.max(max, n);
            return;
        }

        for (int i = 0; i < W; i++) {
            colArr[cnt] = i;
            getCol(cnt + 1);
        }
    }

    private static int shoot() {
        int n = 0;

        for (int i = 0; i < N; i++) {
            n += breakBrick(colArr[i]);
        }

        return n;
    }

    private static int breakBrick(int col) {
        int res = 0;
        int row = -1;
        for (int i = 0; i < H; i++) {
            if (copy[i][col] != 0) {
                row = i;
                break;
            }
        }
        if (row == -1) {
            return 0;
        }

        Queue<int[]> q = new LinkedList<>();
        boolean[][] visit = new boolean[H][W];
        q.add(new int[]{row, col});
        visit[row][col] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int num = copy[cur[0]][cur[1]];
            copy[cur[0]][cur[1]] = 0;
            res++;
            for (int i = 0; i < 4; i++) {
                int nextR = cur[0];
                int nextC = cur[1];
                for (int j = 1; j < num; j++) {
                    nextR += dr[i];
                    nextC += dc[i];

                    if (nextR >= 0 && nextC >= 0 && nextR < H && nextC < W) {
                        if (copy[nextR][nextC] != 0 && !visit[nextR][nextC]) {
                            q.add(new int[]{nextR, nextC});
                            visit[nextR][nextC] = true;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < W; i++) { // 부서진칸 채우기
            int idx = H - 1;
            for (int j = H - 1; j >= 0; j--) {
                if (copy[j][i] == 0) {
                    continue;
                }
                copy[idx][i] = copy[j][i];
                idx--;
            }
            for (int k = idx; k >= 0; k--) {
                copy[k][i] = 0;
            }
        }

        return res;
    }
}