1. 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/92344
2. 문제
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함수를 완성해 주세요.
3. 제한사항
- 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이상이면 파괴되지 않은 건물입니다.
입출력 예
4. 소스코드
import java.util.*;
class Solution {
public int solution(int[][] board, int[][] skill) {
int answer = 0;
int[][] prefixSum = new int[board.length + 1][board[0].length + 1];
for(int[] s : skill) {
int x1 = s[1], y1 = s[2], x2 = s[3], y2 = s[4];
int degree = (s[0] == 2) ? s[5] : -s[5];
prefixSum[x1][y1] += degree;
prefixSum[x1][y2 + 1] += -degree;
prefixSum[x2 + 1][y1] += -degree;
prefixSum[x2 + 1][y2 + 1] += degree;
}
for(int i = 0; i < prefixSum.length - 1; i++) {
for(int j = 1; j < prefixSum[i].length - 1; j++) {
prefixSum[i][j] += prefixSum[i][j - 1];
}
}
for(int i = 0; i < prefixSum[0].length - 1; i++) {
for(int j = 1; j < prefixSum.length - 1; j++) {
prefixSum[j][i] += prefixSum[j - 1][i];
}
}
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
if(board[i][j] + prefixSum[i][j] > 0)
answer++;
}
}
return answer;
}
}5. 접근
- 해당 문제는 누적합을 이용하여 풀이합니다.
- 예를 들어 위 예시와 같이 4x5 배열에서 (0, 0)에서 (2, 2)까지 s를 더하고 싶다고 한다면 아래와 같이 s를 배치해줍니다.
[s, 0, 0, -s, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
-s, 0, 0, s, 0] - 위 배치를 수식으로 표현하면 아래와 같습니다.
- (r1, c1) = s
- (r1, c2 + 1) = -s
- (r2 + 1, c1) = -s
- (r2 + 1, c2 + 1) = s
- 위처럼 배치를 한 이후에 가로로 누적합을 구하고 세로로 누적합을 구해주면 (0, 0)에서 (2, 2)까지 s를 더한 값들이 나옵니다.
- 우선 가로로 누적합을 구합니다.
[s, s, s, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 0, 0
-s, -s, -s, 0, 0] - 가로로 누적합을 하여 구한 결과를 다시 세로로 누적합을 합니다.
[s, s, s, 0, 0
s, s, s, 0, 0
s, s, s, 0, 0
0, 0, 0, 0, 0] - 세로로 누적합을 한 결과를 보면 (0, 0)부터 (2, 2)까지 s가 더해진 것을 볼 수 있습니다.
- 이러한 방법을 이용해 주어진 입력들을 수행하면서 최종적으로 파괴되지 않은 건물의 개수를 구합니다.
- 주어진 적의 공격 혹은 아군의 아군의 회복 스킬을 수행하며 각 위치에 최종적으로 얼만큼의 공격 또는 회복이 적용됐는지 확인합니다.
- 주어진 적의 공격 혹은 아군의 회복 스킬을 계산할 2차원 배열 prefixSum을 생성합니다. 이 때, 위에서 말한 누적합 방법을 이용할 것인데 이는 주어진 (x, y) 좌표에 1을 더한 위치를 이용하기 때문에 board만큼의 크기가 아닌 가로, 세로로 board의 크기보다 1씩 더 큰 크기로 배열을 생성합니다.
- 주어진 (r1, c1), (r2, c2)를 각각 변수 x1, y1, x2, y2에 넣어주고 만약 type이 1이라면 적의 공격을 의미하므로 degree에 (-1)을 곱해주며 type이 2라면 degree를 그대로 가져와 degree에 넣어줍니다.
- 위에서 말한 누적합 방법대로 degree를 배치해줍니다.
- prefixSum의 가로 누적합을 구합니다.
- prefixSum의 세로 누적합을 구합니다.
- board의 각 위치를 확인하면서 해당 위치의 board 값과 prefixSum 값을 더하여 해당 값이 0보다 크다면 건물이 파괴되지 않은 것이므로 파괴되지 않은 건물 개수를 나타내는 변수 answer에 1 더해줍니다.
- 4번에서 모든 위치를 확인한 이후에 answer를 반환합니다.
