[BaekJoon] 20543 폭탄 던지는 태영이 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/20543

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int landSize;
    static int bombRange;
    static long[][] heights;
    static long[][] prefixSum;
    static long[][] answer;

    static void input() {
        Reader scanner = new Reader();

        landSize = scanner.nextInt();
        bombRange = scanner.nextInt();
        heights = new long[landSize][landSize];
        prefixSum = new long[landSize][landSize];
        answer = new long[landSize][landSize];

        for (int row = 0; row < landSize; row++) {
            for (int col = 0; col < landSize; col++) {
                heights[row][col] = scanner.nextInt();
            }
        }
    }

    /*
     * 폭탄의 폭발 범위가 땅을 넘어가게 던지지 않는다고 하였으므로 단순히 M x M 크기의 정사각형의 중심을
     * (M / 2, M / 2)부터 (N - (M / 2 + 1), N - (M / 2 + 1))까지 이동해보며
     * M x M 크기의 정사각형의 (0, 0) 위치의 높이만큼의 폭탄을 M x M 크기의 정사각형의 중심 위치에 놓으면 된다
     * 그러나 이 작업을 그냥 진행하면 시간초과가 일어난다
     *  -> 그러므로 누적합을 이용한다
     *
     * 2차원 배열의 누적합을 나타내는 2차원 배열의 변수명을 prefixSum이라고 한다면, prefixSum의 의미는 아래와 같다
     *  - prefixSum[x][y] = (0, 0)부터 (x, y)까지의 직사각형 내에 있는 폭탄 개수들의 누적합
     *
     * 특정 위치에 있는 M x M 크기의 정사각형의 (0, 0) 좌표를 (r, c)라고 한다면
     * 해당 M x M 크기의 정사각형의 중심은 (r + M / 2, c + M / 2)가 된다
     * 그러므로 N x N 크기의 땅에서 (r, c) 위치에 해당하는 폭탄의 개수는 (r + M / 2, c + M / 2)에 저장하면 된다
     *
     * 누적합을 이용하기로 했기 때문에 위에서 설명한 prefixSum 배열을 이용하여 (r, c) 위치에 해당하는 폭탄의 개수를 구할 것인데
     * 이는 (r, c) 위치에 영향을 미치는 폭탄들의 개수를 모두 더한 후에 -(해발 고도 + 누적 폭탄 개수)를 구하면 된다
     *
     * (r, c) 위치에 영향을 미치는 M x M 크기의 정사각형의 중심은 (r - M / 2, c - M / 2)부터 (r + M / 2, c + M / 2)까지의 직사각형 내에 있는 모든 중심이다
     * 그러므로 누적합을 이용해 (r, c) 위치에 영향을 미치는 폭탄 개수들의 합을 구한다
     *  - 아직 (r + M / 2, c + M / 2) 위치에 둘 폭탄 개수는 알지 못하기 때문에
     *  - 해당 위치는 0으로 두고 (r - M / 2, c - M / 2)부터 (r + M / 2, c + M / 2)까지의 폭탄 개수의 누적합을 구한다
     *  - 이를 구하려면
     *      - 1. (0, 0)부터 (r + M / 2, c + M / 2)까지의 누적합을 구한 후,
     *      - 2. 영향을 미치지 않는 부분의 합을 빼주면 된다
     *  - 우선 1번을 구하려면 아래와 같은 공식을 이용한다
     *      - prefixSum[r + M / 2][c + M / 2] = prefixSum[r - M / 2 - 1][c - M / 2] + prefixSum[r - M / 2][c - M / 2 - 1]
     *                  - prefixSum[r - M / 2 - 1][c - M / 2 - 1]
     *  - 이후 2번을 구하려면 아래와 같은 공식을 이용한다
     *      - prefixSum[r + M / 2][c + M / 2] - (prefixSum[r - M / 2 - 1][c + M / 2] + prefixSum[r + M / 2][c - M / 2 - 1]
     *                  - prefixSum[r - M / 2 - 1][c - M / 2 - 1]
     * 
     * 2번 과정에 해당하는 값을 x라고 칭하면 x에는 (r + M / 2, c + M / 2)에 놓일 폭탄 개수를 제외한 (r, c)에 영향을 미치는 폭탄 개수의 합이 저장되어 있을 것이다
     * 그럼 (r + M / 2, c + M / 2)에 놓일 폭탄의 개수는 -((r, c)의 값 + x)가 된다
     * 이렇게 구한 값을 prefixSum[r + M / 2][c + M / 2]에 더해줘 누적합을 해나간다
     */
    static void solution() {
        if (bombRange == 1) {
            StringBuilder sb = new StringBuilder();
            for (int row = 0; row < landSize; row++) {
                for (int col = 0; col < landSize; col++) {
                    sb.append(-heights[row][col]).append(' ');
                }
                sb.append('\n');
            }
            System.out.println(sb);
            return;
        }
        calculatePrefixSum();
        print();
    }

    static void print() {
        StringBuilder sb = new StringBuilder();
        for (int row = 0; row < landSize; row++) {
            for (int col = 0; col < landSize; col++) {
                sb.append(answer[row][col]).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

    static void calculatePrefixSum() {
        for (int row = 0; row < landSize; row++) {
            for (int col = 0; col < landSize; col++) {
                int[] bombLoc = findBombLoc(row, col);
                int[] unnecessaryLoc = findUnnecessaryLoc(row, col);
                if (bombLoc[0] >= landSize || bombLoc[1] >= landSize) {
                    continue;
                }

                prefixSum[bombLoc[0]][bombLoc[1]] =
                        prefixSum[bombLoc[0] - 1][bombLoc[1]] + prefixSum[bombLoc[0]][bombLoc[1] - 1] - prefixSum[
                                bombLoc[0] - 1][bombLoc[1] - 1];
                long bombCount = -(prefixSum[bombLoc[0]][bombLoc[1]] - (
                        prefixSum[unnecessaryLoc[0]][bombLoc[1]] + prefixSum[bombLoc[0]][unnecessaryLoc[1]]
                                - prefixSum[unnecessaryLoc[0]][unnecessaryLoc[1]]) + heights[row][col]);
                answer[bombLoc[0]][bombLoc[1]] = bombCount;
                prefixSum[bombLoc[0]][bombLoc[1]] += bombCount;
            }
        }
    }

    static int[] findBombLoc(int row, int col) {
        return new int[]{row + bombRange / 2, col + bombRange / 2};
    }

    static int[] findUnnecessaryLoc(int row, int col) {
        int unnecessaryLocX = row - (bombRange / 2 + 1);
        int unnecessaryLocY = col - (bombRange / 2 + 1);
        if (unnecessaryLocX < 0) {
            unnecessaryLocX = 0;
        }
        if (unnecessaryLocY < 0) {
            unnecessaryLocY = 0;
        }

        return new int[]{unnecessaryLocX, unnecessaryLocY};
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}