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

🔗 문제

코딩테스트 연습 - 파괴되지 않은 건물

프로그래머스

 

🖍 풀이

 

무식하게 BF로 풀면 시간초과가 난다. 누적합이라는 새로운 개념이 필요하며 아래 공식 블로그에서 정말 자세하게 설명하고 있다.

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

 

💾  소스

#include <string>
#include <vector>

using namespace std;
int map[1001][1001];

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    int n = board.size();
    int m = board[0].size();
    
    //1. 누적합 준비
    for(int i=0; i<skill.size(); i++)
    {
        int degree = skill[i][5];

        if(skill[i][0] == 1)
            degree*=-1;
        
        map[skill[i][1]][skill[i][2]] += degree;
        map[skill[i][3]+1][skill[i][4]+1] += degree;

        map[skill[i][1]][skill[i][4]+1] -= degree;
        map[skill[i][3]+1][skill[i][2]] -= degree;
    }
    
    //2. 누적합
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<=m; ++j)
        {
            map[i][j]+=map[i-1][j];
        }
    }
    for(int i=0; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            map[i][j]+=map[i][j-1];
        }
    }
    
    //3. 파괴되지 않은 건물 세기
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            if(board[i][j] + map[i][j] > 0)
                ++answer;
        }
    }
    
    return answer;
}