[SWEA/Java] 5656. 벽돌 깨기

[SWEA/Java] 5656. 벽돌 깨기

SW Expert Academy

---

문제 해석

특정 구조의 격자에서 N번의 기회로 최대한 많은 벽돌을 깨뜨리는 시뮬레이션 게임이다. 벽돌은 숫자로 표시되며, 숫자는 벽돌이 폭발할 때 영향을 미치는 범위를 의미한다. 사용자는 N번의 기회에 W의 너비 중 하나를 선택해 벽돌을 발사할 수 있으며, 목표는 격자판에 남은 벽돌의 수를 최소화하는 것이다.

풀이 과정

1. 입력 받기: 테스트 케이스 수와 각 테스트 케이스에 대한 N, W, H, 그리고 격자판 상태를 입력 받는다.
2. 시뮬레이션 실행: 각 위치에서 발사 가능한 모든 조합을 시도하면서 최소 벽돌 수를 찾는다.
   • 순열 생성: N번의 발사를 위한 위치를 순열로 생성한다.
   • 발사 및 폭발: 선택된 위치에서 발사하여 벽돌을 폭발시킨다.
   • 격자 업데이트: 폭발 후 빈 공간을 처리하여 격자를 업데이트한다.
3. 결과 출력: 각 테스트 케이스마다 남은 벽돌의 최소 수를 출력한다.

코드

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

public class Solution {
    private static int N, W, H; // 발사 횟수, 격자판의 너비와 높이
    private static int[][] map, original; // 현재 격자판과 원본 격자판
    private static int[] sel; // 발사할 위치를 저장하는 배열
    private final static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 상,하,좌,우 이동
    private static boolean[][] v; // 방문 체크 배열
    private static int ans; // 남은 벽돌의 최소 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int T = 1; T <= TC; T++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            map = new int[H][W];
            original = new int[H][W];
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    original[i][j] = map[i][j];
                }
            }
            sol(); // 솔루션 함수 실행
            sb.append("#").append(T).append(" ").append(ans).append("\n"); // 결과 기록
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        ans = Integer.MAX_VALUE; // 최소 벽돌 수 초기화
        sel = new int[N]; // 발사할 위치 초기화
        permutation(0); // 순열 생성 및 시뮬레이션
    }

    private static void permutation(int k) {
        if (k == N) {
            for (int s : sel) shoot(0, s); // 순열 완성 후 발사 실행
            ans = Math.min(ans, count()); // 남은 벽돌 수 계산
            setOriginal(); // 원본 격자판 복구
            return;
        }

        for (int i = 0; i < W; i++) {
            sel[k] = i; // 발사 위치 선택
            permutation(k + 1); // 다음 위치 선택을 위한 재귀 호출
        }
    }

    private static void setOriginal() {
        for (int i = 0; i < H; i++) {
            map[i] = original[i].clone(); // 원본 격자판으로 복구
        }
    }

    private static int count() {
        int cnt = 0;
        for (int[] mx : map) {
            for (int my : mx) {
                if (my != 0) cnt++; // 0이 아닌 벽돌 수 계산
            }
        }
        return cnt;
    }

    private static void shoot(int x, int y) {
        if (x == H) return; // 범위 밖 처리

        if (map[x][y] == 0) shoot(x + 1, y); // 빈 공간이면 다음 행 탐색
        else {
            bomb(x, y); // 폭발 실행
            update(); // 격자 업데이트
        }
    }

    private static void update() {
        for (int y = 0; y < W; y++) {
            int cur = H - 1;
            for (int x = H - 1; x >= 0; x--) {
                if (v[x][y]) continue; // 방문한 적이 있으면 건너뜀
                map[cur][y] = map[x][y];
                cur--;
            }
            for (int c = cur; c >= 0; c--) {
                map[c][y] = 0; // 위쪽 빈 공간은 0으로 채움
            }
        }
    }

    private static void bomb(int x, int y) {
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(x, y));
        v = new boolean[H][W];
        v[x][y] = true; // 방문 처리

        while (!q.isEmpty()) {
            Point p = q.poll();
            for (int depth = 1; depth <= map[p.x][p.y] - 1; depth++) {
                for (int[] d : direction) {
                    int nx = p.x + d[0] * depth;
                    int ny = p.y + d[1] * depth;
                    if (nx < 0 || ny < 0 || nx >= H || ny >= W) continue; // 범위 검사
                    if (map[nx][ny] == 0 || v[nx][ny]) continue; // 이미 방문했거나 0이면 건너뜀

                    v[nx][ny] = true;
                    q.offer(new Point(nx, ny)); // 새로운 위치 큐에 추가
                }
            }
        }
    }

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 𝑂(𝑊^𝑁×𝐻×𝑊)로, 순열을 생성하여 각 발사 위치에서 격자를 업데이트하고 폭발 처리를 반복하기 때문에 계산량이 매우 크다. 최악의 경우, 모든 발사 위치 조합과 격자의 모든 셀을 검사해야 한다.

느낀점

이 문제는 벽돌 깨기 게임을 통해 순열과 시뮬레이션을 결합한 복잡한 문제 해결 방식을 경험할 수 있었다. 다양한 시나리오를 시뮬레이션하면서 문제를 해결하는 과정에서 여러 알고리즘 기법을 적용해보는 실력 향상에 큰 도움이 되었다.