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

2차원 IMOS 알고리즘 문제다!

현대오토에버 코테에서 IMOS 알고리즘을 처음 알게 되었는데, 2차원이 조금 더 복잡하다.

가로 누적합 후 세로 누적합을 할 때, 건물에 영향을 받지 않는 지역이 0이 되게 하면 된다.

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int N = board.length;
        int M = board[0].length;
        
        int[][] acc = new int[N + 1][M + 1];
        
        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 power = skill[i][5];
                
            power = (type == 2) ? power : -power;
                
            acc[r1][c1] += power;
            acc[r1][c2 + 1] -= power;
            acc[r2 + 1][c1] -= power;
            acc[r2 + 1][c2 + 1] += power;

        }
        
        for(int i = 0; i < N + 1; i++) {
            for(int j = 1; j < M + 1; j++) {
                acc[i][j] += acc[i][j - 1];
            }
        }

        for(int j = 0; j < M + 1; j++) {
            for(int i = 1; i < N + 1; i++) {
                acc[i][j] += acc[i - 1][j];
            }
        }
        
        int count = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(acc[i][j] + board[i][j] > 0) count++;
            }
        }
        
        return count;
    }
}