[2022 KAKAO BLIND RECRUITMENT] 파괴되지 않은 건물

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92344

이 문제는 누적합을 이용해서 풀 수 있습니다. 이 문제의 경우 단순 완전 탐색 방식으로 풀게 된다면 최대 1000X1000X250000 으로 시간 초과가 발생합니다. 따라서 이 문제는 반복문을 최소화하면서 문제를 풀 수 있는 방법을 사용해야 합니다.

이를 해결할 수 있는 방법이 누적합을 이용한 방법입니다. 매번 해당 범위를 탐색해서 값을 수정하는 대신 특정값만 값을 변경한 후 모든 값이 반영된 누적합 행렬을 계산한 후 이를 한번에 원본 행렬에 계산하는 방식으로 진행합니다. 이 때 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는 (x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같기 때문에 스킬의 개수만큼만 반복함으로 누적합 행렬을 계산할 수 있는 기저 행렬을 구할 수 있습니다. 이를 행 방향, 열 방향으로 이동시키며 누적합을 계산하고 이를 원본 행렬과 계산하면 문제를 풀 수 있습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int N = board.length;
        int M = board[0].length;
        
        int[][] tmp = new int[N+1][M+1];
        
        // 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는 (x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같습니다.
        for(int i=0;i<skill.length;i++){
            int type = skill[i][0];
            int r1 = skill[i][1];
            int c1 = skill[i][2];
            int r2 = skill[i][3];
            int c2 = skill[i][4];
            int degree = skill[i][5];
            
            if(type==1) degree *= -1;
            
            tmp[r1][c1] += degree;
            tmp[r1][c2+1] -= degree;
            tmp[r2+1][c1] -= degree;
            tmp[r2+1][c2+1] += degree;
        }
        
        // 누적합을 이용해서 N*M 행렬을 한 번만 탐색 진행
        for(int i=0;i<=N;i++){
            // 가로 방향 누적합 계산
            for(int j=1;j<=M;j++){
                tmp[i][j] += tmp[i][j-1];
            }
        }
        for(int i=0;i<=M;i++){
            // 세로 방향 누적합 계산
            for(int j=1;j<=N;j++){
                tmp[j][i] += tmp[j-1][i];
            }
        }     
        
        int answer = 0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                board[i][j] += tmp[i][j];
                if(board[i][j]>0) answer++;
            }
        }
        
        return answer;
    }
}