[프로그래머스] 파괴되지 않은 건물 풀이 (2022 카카오 코딩테스트)

| |
프로그래머스 - 파괴되지 않은 건물 C++ 풀이 (2022 카카오 블라인드 채용 1차 코딩테스트)


문제 설명

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다. 예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.


제한사항

  • 1 ≤ board의 행의 길이 (= N) ≤ 1,000
  • 1 ≤ board의 열의 길이 (= M) ≤ 1,000
  • 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
  • 1 ≤ skill의 행의 길이 ≤ 250,000
  • skill의 열의 길이 = 6
  • skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
    • type은 1 혹은 2입니다.
      • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
      • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
    • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
      • 0 ≤ r1 ≤ r2 < board의 행의 길이
      • 0 ≤ c1 ≤ c2 < board의 열의 길이
      • 1 ≤ degree ≤ 500
      • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
      • type이 2이면 degree만큼 건물의 내구도를 높입니다.
  • 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.


풀이

정확성 테스트 통과는 그 어느 문제보다도 쉬운 문제였지만 효율성 테스트가 까다로웠던 문제이다. 사실상 이 문제는 아냐 모르냐가 중요했다. 비슷한 문제를 풀어봤다면 약간의 고민으로 빠르게 풀어낼 수 있었을 것이며, 그렇지 않다면 시험장에서 풀이를 떠올리기 힘들었을 것이다. 그렇다. 고인물들이 흔히 말하는 well-known 문제였다.

먼저 본 문제를 한 문장으로 정의하자면 변화량을 누적시킨 이차원 배열을 구하는 문제이다. 이 배열을 구한 뒤 원본 배열에 해당 배열의 값들을 더하기만 하면 바로 파괴되지 않은 건물들의 갯수를 쉽게 구할 수 있다.

가장 단순하게 생각해보자. skill 배열을 하나 읽을 때마다 바로바로 원본 배열에 반영한다고 가정해보자. 이때 격자의 최대 크기는 1000 * 1000이고 skill 배열의 최대 길이는 250,000이므로 시간복잡도는 O(NMQ) 로 최악의 경우 2천5백억만큼의 연산을 수행하게 될 수도 있다. 따라서 이 방법은 아웃이다.

이 문제 유형을 아예 모르는 상태에서 힌트를 끌어낼만한 조건은 다음과 같이 두 가지이다.

  • 한 번의 skill 마다 격자 모양으로 균일한 변화량이 발생한다
  • 내구도가 음수가 되어 건물이 파괴되어도 변화량은 계속 누적된다

첫 번째 조건을 통해서 “변화량이 균일하니까 격자를 전부 돌지 않고도 격자에 변화량을 표시할 수 있는 방법이 있지 않을까?” 를 떠올힌 후, 두 번째 조건을 통해 “이차원 배열 누적합의 응용 문제겠구나!” 를 예상해야 한다. 사실 여기까지 떠올린다고 해도 아래에서 설명할 방법을 생각해내는게 쉬워보이지는 않는다. 앞서 말했듯이 이 문제는 알면 풀었고 모르면 못 풀었을 확률이 높다.

결론부터 말하면, 격자 모양의 균일한 변화량을 이차원 배열에 적절히 표현한 뒤, 이 배열을 누적합하면 그 동안 해당 영역에 계산되었던 모든 변화량이 누적된 배열을 얻을 수 있다. 이 배열을 원본 배열에 그대로 인덱스를 맞춰 더해주면 답을 구할 수 있다. 그럼 이제 어떻게 적절히 표현하면 되는지 알아보자.

본 문제의 일차원 배열 버전이라고 할 수 있는 문제가 백준에 수록되어 있다.

일차원 배열 arr의 연속적인 구간에 특정 값만큼 더하는 작업을 여러 번 한다고 가정하고, A[n]이 arr[0]부터 arr[n]까지의 누적합을 의미하는 배열 A를 구한다고 가정해보자. 이때, 배열 arr의 i번 칸부터 j번 칸까지 k를 더했다고 가정하고 누적합 배열을 구하기 위해 A에 작업 구간의 시작점인 i번 칸에 k를 더하고 구간이 끝나고 새로운 구간이 시작되는 지점인 j + 1번 칸에 k를 빼보자. 이후 배열 A의 첫번째 요소부터 누적합을 진행하면 i..j 구간 동안만 k가 더해지고, j + 1 이후의 구간은 -k로 인해 앞의 k가 상쇄되어 변화가 없음을 알 수 있다! 즉, 길이가 N인 일차원 배열의 변화량을 누적하는 작업의 시간복잡도를 O(N)에서 O(2), 즉 상수 시간으로 줄일 수 있다.

이와 같은 아이디어를 이차원으로도 어렵지 않게 확장할 수 있다. (r1,c1)부터 (r2,c2)까지의 직사각형에만 변화량 d를 누적하려면 새로운 이차원 배열에서 (r1,c1)에 d를 더하고, (r2 + 1, c1)와 (r1, c2 + 1)에 d를 빼주고 d가 중복해서 2번빠진 구간인 (r2 + 1, c2 + 1)에 d를 다시 더해주면 된다. 이것이 바로 위에서 언급한 이차원 배열에서 변화량을 적절히 표현하는 방법이다.

이제 이 이차원 배열을 누적합해주면 최종적인 배열을 얻을 수 있다. 다행히 이차원 배열의 누적합은 DP를 이용한 최적화 방법이 널리 알려져있고, 아마 대부분 DP 연습문제를 돌리다 한 번 쯤은 풀어봤을 것이다. dp[i][j]를 이차원 배열 A의 (0, 0)부터 (i, j)까지의 누적합이라고 할 때 다음과 같은 점화식이 성립한다.

dp[i][j] = A[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

아이디어는 매 칸마다 해당 칸에 바로 직전 열과 행에 대한 누적합을 더해주고, 중복해서 더해진 누적합 영역을 빼주는 방식이다. 이차원 배열 누적합 문제는 백준에서도 흔히 볼 수 있다. 가장 나이브한 문제는 다음과 같다.

이렇게 누적합까지 진행해주면 최종적으로 모든 변화량이 누적된 배열을 얻을 수 있다. 이제 이 배열을 원본 배열에 더하기만 하면 답을 구할 수 있다. 결론적으로 문제에서 요구하는 작업을 나열하면 N*M 크기의 이차원 배열에 대하여 변화량 배열을 만든 뒤 그에 대한 누적합을 구하고 Q 개의 쿼리에 대한 답을 내는 것이었다. O(NM+Q) 의 시간복잡도로 최악의 경우에도 2 * 1,000 * 1,000 + 250,000 번의 연산으로 여유롭게 효율성 테스트를 통과할 수 있다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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>> delta(N+2, vector<int>(M+2)); // 변화량 누적합 배열
    
    for(auto v:skill) {
        int type = v[0];
        int r1 = v[1], c1 = v[2];
        int r2 = v[3], c2 = v[4];
        int degree = v[5];
        
        if(type == 1) degree = -degree;
        
        // 변화량 누적
        delta[r1+1][c1+1] += degree;
        delta[r2+2][c1+1] -= degree;
        delta[r1+1][c2+2] -= degree;
        delta[r2+2][c2+2] += degree;
    }

    // 누적합 계산
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
            delta[i][j] = delta[i][j] + delta[i-1][j] + delta[i][j-1] - delta[i-1][j-1];
    
    // 건물 파괴 여부 확인
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            if(board[i][j] + delta[i+1][j+1] > 0)
                answer++;

    return answer;
}
0%