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

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

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

해설

처음에 그래프적 이론으로 접근하였다가 효율성 0점을 맞았다.

이것저것 고민해보다 도저히 효율성을 어떻게 통과해야할지 아이디어가 떠오르지 않아 해설을 보았다.

전현서님의 해설이 정말 잘 설명되어 있어서 이를 통해 풀 수 있었다. (링크)

이 문제는 누적합 문제이다.

그렇다면 누적합이란 무엇인가?

누적합

부분합, 누적합이라고 불리는 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있게 해주는 스킬이다.

N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(n)이 걸리는데, 부분합을 이용하면 모든 부분합을 O(1)에 바로 구할 수 있다는 장점이 있다!

1차원 배열

arr을 순차 탐색하면서 sum배열을 만들어 준다.
sum[i]에는 arr[0] + arr[1] + ... + arr[i-1]의 정보가 담겨있다.

또한, 부분 합을 구하고자 할때는 sum배열을 이용해 구할 수 있다.
배열 arr의 i항부터 j항까지의 합을 S(i,j)라고 하자.
S(i,j) = sum[j+1] - sum[i]가 된다.

2차원 배열

2차원 배열은 직관적으로 이해하기에는 다소 어려운 부분이 있다.
하지만 기본 개념은 1차원 배열과 크게 다르지 않다.

arr을 순차 탐색 하면서 sum 배열을 만들어 주면 된다.

이때 sum[i][j]에는 arr[0][0] 부터 arr[i-1][j-1]까지의 합이 담겨있다고 생각하면 된다.

마찬가지로 sum 배열을 활용하면 2차원 배열에서도 상수 시간에 구간합을 구할 수 있다.
arr의 (r1,c1)부터 (r2,c2)까지 합을 S라 할때,
S = sum[r2+1][c2+1] - sum[r1][c2+1] - sum[r2+1][c1] + sum[r1][c1] 으로 구할 수 있다.

문제 풀이

다시 문제로 돌아와서
2차원 배열을 바로 설명하자면 복잡하니 1차원 배열로 보자.

[1, 3, 5, 5]와 같은 1차원 배열이 있다. 여기서 0부터 2번 인덱스까지 2만큼의 피해를 준다 하자. 그렇다면 결과는 [-1, 1, 3, 5]와 같이 된다.

하지만, 대부분의 사람들이 이를 구현할 때 전부 탐색하여 O(n)의 시간 복잡도를 사용한다.
누적합을 응용한 방법을 사용하면 더 빠르게 구현할 수 있다.

우선 위 배열과 길이가 같은 값이 0으로 초기화된 배열을 생성한다. [0, 0, 0, 0]

시작 부분에 빼려는 값을 넣고, 종료 지점보다 한 칸 뒤에 반대 부호를 가진 값을 넣는다.
즉, 0~2 인덱스 범위에 2만큼 공격을 하고 싶으니 시작은 -2가 될것이고, 종료지점 보다 한 칸 뒤에 반대 부호를 넣어야 하니 3인덱스 지점에 2를 넣는다. [-2, 0, 0, 2]

이제 이 배열을 왼쪽부터 오른쪽으로 누적합을 진행한다.
[-2, -2, 0, 2] -> [-2, -2, -2, 2] -> [-2, -2, -2, 0]

그러면 위와 같이 누적합이 된 배열이 나오게 된다. 이를 기존 배열에 각각 원소마다 더하면,
[1, 3, 5, 5] + [-2, -2, -2, 0] = [-1, 1, 3, 5]
즉, 우리가 원하는 값을 찾을 수 있다.

아마 처음에 이걸 보는 사람은, "아니 결국 다시 저렇게 더할거면, 기존하고 시간복잡도가 다를게 뭐가있냐?" 라고 생각할 것 이다. 필자 또한 그랬었다.
하지만, 누적합의 대단한 점은, 변화하는 값들을 계속 읽어들인 다음에 한 번에 누적합으로
그 변화값의 결과를 낼 수 있다는 점이다.

즉, skill원소 하나당 O(N)의 시간 복잡도가 아닌 O(1)의 시간복잡도로 처리가 가능하다는 의미다.

위의 예시는 하나만 들어서 비효율적으로 보인것이지, 데이터가 여러개있으면, 누적합 연산을 제일 마지막에 한 번만 해주면 끝난다.

자, 이제 2차원 배열에서 어떻게 해야 하는지 알아보자.

만약 4x4배열에서 (0, 0)~(2, 2)까지 n만큼의 변화를 주고싶다면,

[n, 0, 0, -n]
[0, 0, 0, 0]
[0, 0, 0, 0]
[-n, 0, 0, n]

위와 같은 위치에 n을 배치하면 된다.

위의 배열을 오른쪽으로 누적합, 아래쪽으로 누적합 또는 순서를 바꿔도,

[n, n, n, 0]
[n, n, n, 0]
[n, n, n, 0]
[0, 0, 0, 0]

결과가 위와 같이 원하는 범위에 원하는 값만큼 변화시킬 수 있다.

즉 (x1, y1) ~ (x2, y2)까지 n만큼의 변화를 주고 싶다면,
(x1, y1) = n, (x2+1, y1) = -n, (x1, y2+1) = -n, (x2+1, y2+1) = n 만큼의 값을 더해주면, 원하는 부분에 원하는 변화량만큼 값을 바꿀 수 있다.

다시 한 번 (0,0) ~ (2,2)까지 5만큼의 변화를 주는 예시를 통해 이해해보자.

[5, 0, 0, -5]
[0, 0, 0, 0]
[0, 0, 0, 0]
[-5, 0, 0, 5]

먼저 각 행마다 왼쪽에서 오른쪽으로 각각 누적합을 해준다.

[5, 5, 5, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[-5, -5, -5, 0]

그 다음, 각 열마다 위에서 아래로 각각 누적합을 해준다.

[5, 5, 5, 0]
[5, 5, 5, 0]
[5, 5, 5, 0]
[0, 0, 0, 0]

결과를 보면 알 수 있듯이 (0,0) ~ (2,2)까지 5의 증가가 일어난 것을 확인할 수 있다.

이를 통해 우리는 문제를 해결할 수 있다.

1. 우선 반복문을 통해 모든 skill을 조사하여 위의 예시와 같이 arr이라는 배열에 degree를 저장해준다.
   즉, 만약 우리가 건물을 회복해야 한다면,
   (r1, c1) = degree, (r2+1, c1) = -degree, (r1, c2+1) = -degree, (r2+1, c2+1) = degree 만큼의 값을 더해주자.

   type_dict = {1:-1, 2:1}
    arr = [[0 for _ in range(m)] for _ in range(n)]
    psum_arr = [[0 for _ in range(m+1)] for _ in range(n+1)]
    
    for t, r1, c1, r2, c2 , degree in skill:
        arr[r1][c1] += type_dict[t]*degree
        if r2+1 < n: arr[r2+1][c1] -= type_dict[t]*degree
        if c2+1 < m: arr[r1][c2+1] -= type_dict[t]*degree
        if r2+1 < n and c2 + 1 < m : arr[r2+1][c2+1] += type_dict[t]*degree

2. 모든 skill에 대하여 arr에 표식을 저장했으니, 누적합을 진행한다.
   이는 이중 for문을 사용하여 진행한다. 이때 아래 그림과 같이 psum_arr[i][j] 에는 arr[0][0]부터 arr[i-1][j-1]까지의 합이 담겨있다고 생각하면 된다.
   이때 중요한 점은 psum_arr을 만들 때 행과 열이 1씩 더 커야 한다는 점이다.
   왜냐하면 psum_arr[i][j]를 구하기 위해서 arr 배열의 i-1행과 j-1열의 정보를 이용해야 하는데, psum_arr과 arr 배열의 크기가 같게 되면 IndexError 가 발생하기 때문이다.

   for i in range(1, n+1):
        for j in range(1, m+1):
            psum_arr[i][j] = arr[i-1][j-1] + psum_arr[i-1][j] + psum_arr[i][j-1] - psum_arr[i-1][j-1]

3. 모든 skill에 대하여 각 건물의 증감을 해 줄 배열을 구하였다.
   이제는 각 건물에 우리가 구한 증감을 더해주면 끝이다.

    for i in range(n):
        for j in range(m):
            board[i][j] += psum_arr[i+1][j+1]
            if board[i][j] > 0:
                answer += 1

요약하자면 모든 공격 및 회복을 조사하여 한꺼번에 더하기 위해 arr에 위와같은 방법으로 표식을 저장을 하는 것이다. 왜냐하면 후에 누적합을 진행하기 전에 하는 표식은 중복이 되도 전체적인 결과는 동일하다.
이런 특성을 이용해 우리는 기존에 O(KNM)이 걸렸던 시간 복잡도를 O(K+N*M)의 시간복잡도로 엄청나게 단축이 가능해진다.

왜냐하면 skill하나를 가져오는데 O(1)이 걸리고 그 개수가 K만큼 존재하므로 O(K)가 먼저 성립이 된다.

또한 마지막에 누적합을 하기 위해서는 전체배열을 접근해야하므로 O(NM)이 그 뒤에 추가로 더해진다.

최종적으로 O(K+NM)의 시간복잡도로 이 문제를 클리어 할 수 있다.

# 2022 KAKAO BLIND RECRUITMENT

def solution(board, skill):
    answer = 0
    n, m = len(board), len(board[0])
    type_dict = {1:-1, 2:1}
    arr = [[0 for _ in range(m)] for _ in range(n)]
    psum_arr = [[0 for _ in range(m+1)] for _ in range(n+1)]
    
    for t, r1, c1, r2, c2 , degree in skill:
        arr[r1][c1] += type_dict[t]*degree
        if r2+1 < n: arr[r2+1][c1] -= type_dict[t]*degree
        if c2+1 < m: arr[r1][c2+1] -= type_dict[t]*degree
        if r2+1 < n and c2 + 1 < m : arr[r2+1][c2+1] += type_dict[t]*degree
    
    # for i in range(n):
    #     print(*arr[i])
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            psum_arr[i][j] = arr[i-1][j-1] + psum_arr[i-1][j] + psum_arr[i][j-1] - psum_arr[i-1][j-1]
    
    # print("-"*50)
    # for i in range(n+1):
    #     print(*psum_arr[i])
    for i in range(n):
        for j in range(m):
            board[i][j] += psum_arr[i+1][j+1]
            if board[i][j] > 0:
                answer += 1
        
    return answer