파괴되지 않은 건물
문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
NxM 크기의 행렬 모양의 게임 맵이 있습니다. 이 맴에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0 이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 놓이려고 합니다.
적의 공격과 아군의 회복스킬은 항상 정사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4x5인 맴에 내구도가 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만큼 건물의 내구도를 높입니다.
- type은 1 혹은 2입니다.
- 건물이 파괴되었다가 회복 스킬을 받아 내구도가 1 이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1 이상이면 파괴되지 않은 건물입니다.
정확성 테스트 케이스 제한 사항
- 1<=board의 행의 길이(=N)<=100
- 1<=board의 열의 길이(=M)<=100
- 1<=board의 원소(각 건물의 내구도)<=100
- 1<=skill의 행의 길이<=100
- 1<=degree<=100
효율성 테스트 케이스 제한 사항
- 주어진 조건 외 추가 제한사항 없습니다.
풀이
예제 입력
board = [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]]
skill = [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]]
board와 같은 크기의 2차원 배열에 0으로만 채워져 있다고 하자. 스킬 [1,2,0,2,3,2]를 수행한 결과는 아래 그림과 같습니다.
이렇게 각 스킬의 결과를 하나씩 반영해보니, 효율성을 하나도 통과하지 못해 결국 다른 분들의 풀이를 참고해서 풀어보았습니다.
|1차원 배열로 동일한 문제 : Baekjoon 19951. 태상이의 훈련소 생활 풀이|
- 위의 풀이를 2차원 버전으로 생각해보면, 먼저 최종 변경률 배열을 만들 수 있다.
- 먼저 구간별 누적 변경률을 구해보자. 누적 변경률 배열을 dp라고 할 때, dp와 누적합 배열과의 관계는 아래와 같다.
- 따라서, 특정 구간에만 k 값을 더하는 연산은
위의 이미지를 아래 이미지와 같이 누적 변경률 배열(dp)로 만들 수 있으며, 모든 연산이 완료된 이후 누적합 계산을 한 최종 변경률 배열을 얻을 수 있다.
- 이렇게 구한 최종 변경률 배열을 원본 배열과 더한 값이 0보다 크면 파괴되지 않은 건물임을 알 수 있다.
- 그럼 다시 예제로 돌아가 보자.
- skill 배열의 각 스킬들을 순차적으로 적용한 누적 변경률 배열(dp)는 아래와 같으며 누적합을 통해 최종 변동률을 구할 수 있다.
( 이 때, 공격인 경우, 주어진 k값(5번째 원소)가 음수인 점에 유의하자. )
- 구한 최종 변동률 값을 원본 배열인 board에 더해주면,
- 최종 건물들의 내구도를 구할 수 있다.
- 내구도가 0보다 큰 건물의 개수를 구하면 결과를 얻을 수 있다.(result = 10)
코드
def solution(board, skill):
answer = 0
n, m = len(board), len(board[0])
dp = [[0 for _ in range(m+2)] for _ in range(n+2)]
for s in skill :
k = s[5] * (1 if s[0] == 2 else -1)
x1, y1, x2, y2 = s[1]+1, s[2]+1, s[3]+1, s[4]+1
dp[x1][y1] += k
dp[x2+1][y2+1] += k
dp[x1][y2+1] += -k
dp[x2+1][y1] += -k
# 누적합 계산
for i in range(1, n+2) :
for j in range(1, m+2) :
dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
# 건물의 내구도 계산
for i in range(n) :
for j in range(m) :
if board[i][j] + dp[i+1][j+1] > 0 :
answer += 1
return answer