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

문제

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

SW Expert Academy

풀이

주어진 제약 사항

1. 1 ≤ N ≤ 4

2. 2 ≤ W ≤ 12

3. 2 ≤ H ≤ 15

풀기 전 생각

Q. 어디서 구슬을 떨어트려야 최대로 벽돌이 깨지는가?

-> 그럼 어디서 구슬을 떨어트려야 하는가?? => 어디서 최대로 벽돌이 깨지는지 모르니까 하나씩 해보자!!

-> 구슬은 최대 4개까지 떨어지고 W는 최대 12이다. 최악일 경우 12^4 = 20,736번 케이스를 돌아야 한다. 

-> 이 정도는 하나씩 케이스를 돌아도 괜찮다! 그렇다면 초기화를 해줄 배열이 필요하다.

 

동작 순서

1. 구슬을 떨어트린다.

- 구슬을 떨어트릴 순서(어디서부터 떨어트릴지) 구하기

 

2. 상,하,좌,우 로 벽돌들을 부신다. 이때 다른 벽돌들도 영향을 받는다.

- 구슬이 처음으로 깨는 벽돌이 1이면 끝(return)

- 만약 1이 아니면 벽돌의 값에 따라 상, 하, 좌, 우 벽돌을 깬다. (3이면 상, 하, 좌, 우 2씩 깬다.)

  이때 깨지는 벽돌도 마찬가지로 값에 따라 다른 벽돌들이 깨진다. => dfs로 구현?!

- index 값 유의할 것!!

 

3. 빈 공간이 생기면 벽돌을 밑으로 당긴다.

- 전체 열 하나씩 확인하기

 

4. 남은 벽돌 수 세기

---

코드

메인

    static int map[][], tmp[][];
    static int count, n, w, h;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            n = sc.nextInt();
            w = sc.nextInt();
            h = sc.nextInt();
            map = new int[h][w];
            tmp = new int[h][w];

            count = Integer.MAX_VALUE;

            for (int i = 0; i < h; i++)
                for (int j = 0; j < w; j++)
                    map[i][j] = sc.nextInt();

            bombSeq();
            System.out.println("#"+t+" "+count);
        }

    }

bombSeq : 폭탄을 떨어트릴 순서 정하기

    private static void bombSeq() {
        //폭탄을 떨어트릴 순서 넣기 
        for (int i = 0; i < w; i++)
            for (int j = 0; j < w; j++)
                for (int k = 0; k < w; k++)
                    for (int v = 0; v < w; v++)
                        toBomb(i, j, k, v);

    }

toBomb : 순서에 따라 폭탄 터지기

    private static void toBomb(int a, int b, int c, int d) {
        //폭탄 떨어트릴 순서배열
        int seq[] = new int[4];
        seq[0] = a;
        seq[1] = b;
        seq[2] = c;
        seq[3] = d;

        initTmp(); //tmp 배열 초기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < h; j++) {
                if (tmp[j][seq[i]] != 0) {
                    //폭탄 터짐
                    bomb(j, seq[i], tmp[j][seq[i]]);
                    break;
                }
            }
            //빈 공간있으면 down
            down();
        }
        //남은 벽돌 수 세기
        getCount();

    }

bomb : 폭탄 터짐

    private static void bomb(int a, int b, int v) {
        int da[] = {1, -1, 0, 0};
        int db[] = {0, 0, -1, 1};

        tmp[a][b] = 0;
        if (v == 1) return;

        for (int i = 0; i < 4; i++) {
            for (int j = 1; j < v; j++) {
                int tmpA = a + da[i] * j;
                int tmpB = b + db[i] * j;
                if (tmpA >= 0 && tmpA < h && tmpB >= 0 && tmpB < w) {
                    if (tmp[tmpA][tmpB] > 0) {
                        bomb(tmpA, tmpB, tmp[tmpA][tmpB]);
                    }
                }else break;

            }
        }
    }

 

down : 벽돌 밑으로 내리기

    private static void down() {
        for (int i = 0; i < w; i++) {
            for (int j = h - 1; j >= 0; j--) {
                if (tmp[j][i] == 0) {
                    for (int k = j - 1; k >= 0; k--) {
                        if (tmp[k][i] != 0) {
                            tmp[j][i] = tmp[k][i];
                            tmp[k][i] = 0;
                            break;
                        }
                    }
                }
            }

        }

    }

getCount : 남은 벽돌 수 세기

    private static void getCount() {
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++)
                if (tmp[i][j] != 0)
                    cnt++;
        }
        if (cnt < count)
            count = cnt;
    }

initTmp : tmp배열 초기화

    private static void initTmp() {
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                tmp[i][j] = map[i][j];

    }