[프로그래머스] LV3. 파괴되지 않은 건물

문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

필요 알고리즘 개념

누적합 (Prefix Sum)

배열의 특정 구간 합을 빠르게 구하기 위해 사용하는 기법으로 prefixSum[i] = x[0] + x[1] + ... + x[i] 하여 특정 구간의 합을 $O(1)$ 연산으로 빠르게 구할 수 있다.

x = [1, 2, 3]

prefixSum[0] = 1
prefixSum[1] = 1 + 2 = 3
prefixSum[2] = 1 + 2 + 3 = 6

✅ 사용 목적

• 배열의 구간 합을 빠르게 구할 수 있음
• 배열 자체 값은 변경하지 않음

차이배열 (Difference Array)

누적합을 역으로 이용하는 방식으로 배열을 직접 수정하는게 아니라, 변화량(Δ, delta)만 기록 후 나중에 한 번에 계산하는 기법

x = [1, 2, 3, 4, 5]   // [1, 3]에 +2 더하기
x[1] += 2  // 해당 인덱스부터 시작
x[4] -= 2  // 3의 이후 엔덱스부터 -2 하여 원래값 복구
diff = [0, 2, 0, 0, -2]
// 누적합 계산
result[0] = 1
result[1] = result[0] + diff[1] = 1 + 2 = 3
result[2] = result[1] + diff[2] = 3 + 0 = 3
result[3] = result[2] + diff[3] = 3 + 0 = 3
result[4] = result[3] + diff[4] = 3 + (-2) = 1

✅ 사용 목적

• 배열의 특정 구간을 효율적으로 수정할 때 사용
• 배열의 값을 직접 수정하는 게 아니라, 변화량(Δ)을 기록하는 방식

📌결론

• 차이 배열은 변화량 기록
• 누적합을 사용하여 최종 값 계산

💡참고

2차원 배열의 누적합 적용

(r1, c1) ~ (r2, c2)를 업데이트할 때

diff[r1][c1] += X;  // 변화값
diff[r1][c2+1] -= X;  // 복구값
diff[r2+1][c1] -= X;  // 복구값
diff[r2+1][c2+1] += X;  // 두 번 복구된 걸 다시 원복

---

코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int r = board.length; int c = board[0].length;
        // 차이 배열 이용
        int[][] diff = new int[r + 1][c + 1];  // 끝까지 변화하는 경우가 있으므로 + 1
        for (int[] s : skill) {
            int w;
            if (s[0] == 1) w = -s[5] ; else w = s[5];  // 적군이면 -1, 아군이면 1
            diff[s[1]][s[2]] += w;   // 변화량 기록
            diff[s[3] + 1][s[4]] -= w;  // 되돌리기
            diff[s[3]][s[4] + 1] -= w;  // 되돌리기
            diff[s[3] + 1][s[4] + 1] += w;  // 두 번 변화한 것 다시 되돌리기
        }
        // 누적합 구하기
        int[][] prefixSum = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                prefixSum[i][j] = diff[i][j];
                if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j];  // 위쪽 값 추가
                if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1];  // 왼쪽 값 추가
                if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1];  // 중복 제거
            }
        }
        // 파괴되지 않은 건물 찾기
        int count = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] + prefixSum[i][j] > 0) {
                    count++;
                }
            }
        }
        return count;
    }
}