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

문제 링크

문제 정의

• $N * M$의 보드 board가 주어짐

  • board의 각 칸은 벽의 내구도로 초기화

• Skill들이 주어짐

  • 하나의 스킬은 [type, r1, c1, r2, c2, degree]의 형태
  • type은 1 또는 2 (1은 파괴 2는 회복)
  • 좌표 $(r1, c1)$ $(r2, c2)$ 주어짐
  • degree는 회복 또는 파괴 크기

이 때 모든 스킬을 사용했을 때
파괴되지 않은 벽의 수를 구하기

---

접근 방법

시간 복잡도

일반적으로 생각할 수 있는건 하나씩 해보는겁니다.
이걸 시간 복잡도로 따져보자면
$O(N*M*S)$입니다.

이 때 의미는 다음과 같으며

• $N$: board의 행 (최대 $1,000$)
• $M$: board의 열 (최대 $1,000$)
• $S$: 스킬의 수 (최대 $250,000$)

$O(N*M*S) = 1,000 * 1,000 * 250,000 = 250,000,000,000$

당연하게도 시간초과가 발생합니다.

---

누적합 다이나믹 프로그래밍

그러면 어떻게 문제를 풀 수 있을까요?
다이나믹 프로그래밍을 사용하는 것입니다.

우선 해당 문제에서는 dp 대신 prefix라는 이름의 배열을 사용하겠습니다.

prefix[r][c]의 의미가 중요한데
저는 이 prefix[r][c]의 의미를
"(0, 0)부터 (r, c)까지 prefix[r][c]값으로 모두 더해라"로 정했습니다.

그렇게 되면
원래 스킬 하나당 $O(N*M)$이 걸리던 문제를
다이나믹 프로그래밍을 통해 $O(1)$로 문제를 압축할 수 있습니다.

물론 스킬들을 모두 사용하고
추가적인 누적합 연산을 통해 정답을 구해야 하므로
최종 시간 복잡도는 $O(S + N*M)$이 될 것 같습니다.

---

스킬 압축 방식

skill을 누적하는 방식에 대해서는 간단하게 설명했지만
구체적으로 어떤 로직인지 설명하겠습니다.

다음과 같이 board와 prefix가 초기화 되어 있다고 가정하겠습니다.

1. (0, 0) 부터 (3, 4) 까지 4만큼 파괴

스킬은 배열로 들어오지만
이해하기 쉽게 위 소제목처럼 스킬을 풀어서 설명드리겠습니다.

소제목의 스킬을 시뮬레이션을 하면 board처럼 되겠지만
useSkill 메서드를 수행하면
prefix에 단 하나의 좌표에만 값이 변경 되는 것을 알 수 있습니다.

해당 시뮬레이션은 r1과 c1이 모두 0에 해당하는 가장 간단한 케이스입니다.

또 다른 케이스는 두 번, 또는 네 번까지 연산이 필요한 케이스가 있는데
다음 케이스에서 보여드리겠습니다.

---

2. (2,0)부터 (2,3)까지 2만큼 파괴

다음은 r1이 0이 아닌 케이스입니다.

prefix[2][3]에 -2를 누적했지만
이대로 두면 (0, 0)부터 (1,3)까지는 잘못 누적되게 됩니다.

그래서 이 문제를 해결하기 위해
"(0, 0)부터 (1,3)까지" 라는 의미는 prefix[1][3]과 의미가 같으므로
prefix[1][3]에 2를 2를 누적합니다.

즉 r1 > 0이라면
prefix[r1-1][c2] -= degree 연산을 추가로 수행해야 합니다.

---

3. (0, 1)부터 (2, 3)까지 2만큼 회복

다음은 c1이 0이 아닌 케이스입니다.

회복이기 때문에 prefix[2][3]에 2를 누적해 0이 됐지만
이대로 두면 (0, 0)부터 (2,0)까지는 잘못 누적되게 됩니다.

그래서 이 문제를 해결하기 위해
"(0, 0)부터 (2,0)까지" 라는 의미는 prefix[2][0]과 의미가 같으므로
prefix[2][0]에 2를 -2를 누적합니다.

즉 c1 > 0이라면
prefix[r2][c1-1] -= degree 연산을 추가로 수행해야 합니다.

---

4. (1, 1)부터 (2, 3)까지 2만큼 파괴

다음은 r1과 c1 둘 다 0이 아닌 케이스입니다.

파괴이기 때문에 prefix[2][3]에 -2를 누적해 -2이 됐지만
이대로 두면
(0, 0)부터 (2,0)까지 그리고 (0, 0)부터 (0,2)까지는 잘못 누적됩니다.

그래서 이 문제를 해결하기 위해
"(0, 0)부터 (2,0)까지" 라는 의미는 prefix[2][0]과 의미가 같으므로
prefix[2][0]에 2를 2를 누적하고

"(0, 0)부터 (0,2)까지" 라는 의미는 prefix[0][2]과 의미가 같으므로
prefix[0][2]에 2를 2를 누적합니다.

여기서 잘못된 행과 열을 다시 빼주는 연산을 수행할 때
중복되는 좌표가 존재하는데
이 좌표를 다시 정상적으로 복구하려면
prefix[r1-1][c1-1] += degree 연산이 필요합니다.

즉 c1 > 0 이라면 총 4가지 연산을 수행해야 합니다.

• prefix[r2][c2] += degree
• prefix[r1-1][c2] -= degree
• prefix[r2][c1-1] -= degree
• prefix[r1-1][c1-1] += degree

---

역방향 전파

저는 배열의 prefix[r][c] 의미를 ($N-1$, $M-1$)부터 ($r$, $c$)까지로 설계하지 않고
역방향인 ($0$, $0$)부터 ($r$, $c$)까지로 설계했기 때문에
이 로직에 맞게 전파 로직을 설계했습니다.

1단계: 가로 방향 전파 (Right → Left)

for (int i = N - 1; i >= 0; i--) {
    for (int j = M - 1; j >= 1; j--) {
        // 오른쪽 칸의 누적된 변화량을 왼쪽 칸으로 전달
        prefix[i][j - 1] += prefix[i][j];
    }
}

가장 먼저 수행할 작업은
각 행(Row)별로 오른쪽에 찍힌 에너지를 왼쪽으로 전달하는 것입니다.

핵심 동작: 현재 칸(j)의 값을 바로 왼쪽 칸(j-1)에 더해줍니다.

결과: 이 과정을 마치면, useSkill에서 찍었던 (r2, c2)의 플러스 값이 (r2, c1)까지 일직선으로 채워지게 됩니다.

---

2단계: 세로 방향 전파 (Bottom → Top)

for (int j = M - 1; j >= 0; j--) {
    for (int i = N - 1; i >= 1; i--) {
        // 아래쪽 칸의 변화량을 위쪽 칸으로 전달
        prefix[i - 1][j] += prefix[i][j];
    }
}

가로로 길게 늘어난 에너지를 이제 위쪽으로 끌어올렸습니다.
이 단계가 끝나면 원했던 prefix 사각형 형태의 영역이 완성됩니다.

핵심 동작: 아래 칸(i)의 값을 바로 위 칸(i-1)에 더해줍니다.

결과: 가로로 채워졌던 줄들이 위로 복사되면서 (r1, c1)부터 (r2, c2)까지의 면적이 모두 동일한 degree 값을 갖게 됩니다.

---

3단계: 최종 판정 (Data Fusion)

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        // 원본 내구도 + 누적 변화량
        if (board[i][j] + prefix[i][j] <= 0) {
            count++; // 파괴된 건물 카운트
        }
    }
}

모든 전파가 끝난 prefix[i][j]는 해당 칸이 받은 총 변화량(누적 데미지/회복)을 의미합니다.
이제 원본 데이터인 board와 합쳐서 최종 상태를 확인합니다.

---

코드

import java.util.*;

class Solution {
    static int N;
    static int M;
    public int solution(int[][] board, int[][] skills) {
        N = board.length;
        M = board[0].length;
        int[][] prefix = new int[N][M];
        
        for (int[] skill : skills) {
            useSkill(prefix, skill[1], skill[2], skill[3], skill[4], skill[0] == 1 ? -skill[5] : skill[5]);
        }
        
        return getAnswer(board, prefix);
    }
    
    
    static void useSkill (int[][] prefix, int r1, int c1, int r2, int c2, int degree) {
        prefix[r2][c2] += degree;
        
        if (r1 > 0) {
            prefix[r1-1][c2] -= degree;
        }
        
        if (c1 > 0) {
            prefix[r2][c1-1] -= degree;
        }
        
        if (r1 > 0 && c1 > 0) {
            prefix[r1-1][c1-1] += degree;
        }
    }
    
    static int getAnswer (int[][] board, int[][] prefix) {
        int count = N * M;
        for (int i = N-1; i >= 0; i--) {
            for (int j = M-1; j >= 1; j--) {
                prefix[i][j-1] += prefix[i][j];
            }
        }
        
        for (int j = M-1; j >= 0; j--) {
            for (int i = N-1; i >= 0; i--) {
                if (i > 0) {
                    prefix[i-1][j] += prefix[i][j];
                }
                
                if (board[i][j] + prefix[i][j] <= 0) {
                    count--;
                }
            }
        }
        return count;
    }
}