[프로그래머스] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT) : Cpp

프로그래머스 파괴되지 않은 건물 문제입니다.

문제

N x M 형태의 그래프가 주어집니다. 이때, 각 노드는 건물을 의미하고, 숫자는 방어력을 의미합니다.
방어력이 0 이하가 되면 건물은 파괴되고, 1 이상이면 건물은 생존합니다.
이때, 라운드를 거치면서 건물의 방어력을 회복하거나 공격하는 일이 벌어집니다.(건물이 파괴되어도 1 이상의 방어력으로 회복된다면 건물은 다시 생존하게 됩니다.)
라운드를 다 거친 후 생존한 건물의 개수를 출력하시오.

알고리즘 아이디어

이 코드는 GPT에 도움을 받아 작성되었습니다.

1. 한번씩 변화를 모두 업데이트를 한다면 시간초과가 난다.
2. 한번에 변화를 업데이트를 해야 한다.(업데이트 할 그래프가 너무 큼)
3. 따라서 누적합으로 접근해서 풀어내야 한다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n = board.size();
    int m = board[0].size();
    vector<vector<int>> diff(n + 1, vector<int>(m + 1, 0));
    
    for(int i = 0; i < skill.size(); 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 * degree;
        diff[r1][c1] += degree;
        diff[r1][c2 + 1] -= degree;
        diff[r2 + 1][c1] -= degree;
        diff[r2 + 1][c2 + 1] += degree;
    }
    
    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            diff[i][j] += diff[i][j - 1];
        }
    }
    
    for (int j = 0; j < m + 1; j++) {
        for (int i = 1; i < n + 1; i++) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            board[i][j] += diff[i][j];
            if (board[i][j] > 0) answer++;
        }
    }
    return answer;
}

혹시라도 틀린 내용이 있다면 댓글로 지적해주시면 감사하겠습니다!!