[코드트리] 강력한 폭발(Java)

문제 링크

https://www.codetree.ai/missions/2/problems/strong-explosion?&utm_source=clipboard&utm_medium=text

내 코드

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

public class Main {

    // 폭탄 위치를 저장할 클래스
    static class Point {
        int x;
        int y;

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

    // 2번 타입 폭탄용 dx, dy
    static int[] dxs = new int[] {1, 0, -1, 0};
    static int[] dys = new int[] {0, 1, 0, -1};

    // 3번 타입 폭탄용 dx, dy
    static int[] dxs2 = new int[] {1, -1, -1, 1};
    static int[] dys2 = new int[] {1, 1, -1, -1};

    // 폭탄을 터뜨리거나(bomb = 1) 복원하는(bomb = -1) 메서드
    static void change(int method, int x, int y, int bomb) {
        bombed[x][y] += bomb;
        switch(method) {
            // 1번 폭탄
            case 0:
                for (int i = x-2; i <= x+2; i++) {
                    if (inRange(i, y)) bombed[i][y] += bomb;
                }
                break;

            // 2번 폭탄
            case 1:
                for (int i = 0; i < 4; i++) {
                    int nx = x + dxs[i];
                    int ny = y + dys[i];
                    if (inRange(nx, ny)) {
                        bombed[nx][ny] += bomb;
                    }
                }
                break;

            // 3번 폭탄
            case 2:
                for (int i = 0; i < 4; i++) {
                    int nx = x + dxs2[i];
                    int ny = y + dys2[i];
                    if (inRange(nx, ny)) {
                        bombed[nx][ny] += bomb;
                    }
                }
                break;
        }
    }

    static boolean inRange(int nx, int ny) {
        return 0 <= nx && nx < n && 0 <= ny && ny < n;
    }

    static void recur(int cnt) {
        if (cnt == bombNum) {
            int res = count();
            max = Math.max(max, res);
            return;
        }

        Point cur = bombs.get(cnt);
        for (int i = 0; i < 3; i++) {
            change(i, cur.x, cur.y, 1);
            recur(cnt+1);
            change(i, cur.x, cur.y, -1);
        }
    }

    static int count() {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (bombed[i][j] > 0) sum++;
            }
        }
        return sum;
    }

    static ArrayList<Point> bombs;
    static int n;
    static int[][] grid;
    static int[][] bombed;
    static int bombNum;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        grid = new int[n][n];
        bombed = new int[n][n];
        bombs = new ArrayList<>();
        StringTokenizer st = null;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int input = Integer.parseInt(st.nextToken());
                grid[i][j] = input;
                if (input == 1) bombs.add(new Point(i, j));
            }
        }
        // 폭탄 개수
        bombNum = bombs.size();

        recur(0);
        System.out.println(max);
    }
}

설명

change()

• method : 폭탄 종류
• x, y : 폭탄 위치
• bomb : 폭탄을 터뜨리는건지(1), 터뜨린 폭탄 복원하는건지(-1)

inRange()

• 매개변수로 넘어온 좌표가 n x n 범위 안에 있는지 판단

recur()

• 각 종류별로 터뜨려보고 다시 복원하는 재귀함수
• 이름 짓기 어려워서 그냥 recur 이라고 함…ㅋㅋ
• 모든 폭탄 다 터뜨려봤다면 count() 메서드를 통해 초토화 영역 개수 세기
• 최댓값만 max에 저장

count()

• 초토화된 영역 개수 반환하는 메서드

main()

• 입력을 받으면서 폭탄 위치를 bombs 라는 리스트에 저장해놓음
  • 매번 폭탄 위치 찾지 않기 위해서