문제 요약
N x M 크기의 게임 맵에 건물이 있고, 각 칸에는 내구도가 있다.
스킬은 두 종류다.
type = 1: 공격, 내구도 감소
type = 2: 회복, 내구도 증가각 스킬은 항상 직사각형 범위에 적용된다.
모든 스킬을 적용한 뒤 내구도가 1 이상인 건물의 개수를 구해야 한다.
핵심 아이디어
스킬마다 직사각형 내부의 모든 칸을 직접 갱신하면 시간이 너무 오래 걸린다.
예를 들어 N, M, skill의 개수가 모두 크다면 다음 방식은 비효율적이다.
for skill in skills:
for i in range(r1, r2 + 1):
for j in range(c1, c2 + 1):
board[i][j] += degree따라서 2차원 누적합을 사용한다.
정확히는 직사각형 범위 갱신을 빠르게 처리하기 위해 2차원 차이 배열을 만든다.
2차원 차이 배열
직사각형 (r1, c1)부터 (r2, c2)까지 값 degree를 더하고 싶다고 하자.
차이 배열 diff에 다음 네 곳만 갱신한다.
diff[r1][c1] += degree
diff[r1][c2 + 1] -= degree
diff[r2 + 1][c1] -= degree
diff[r2 + 1][c2 + 1] += degree이후 행 방향 누적합과 열 방향 누적합을 차례로 구하면 각 칸에 실제로 더해져야 할 값이 계산된다.
공격과 회복 처리
공격은 내구도를 감소시키므로 음수로 처리한다.
회복은 내구도를 증가시키므로 양수로 처리한다.
if type == 1:
degree = -degree이렇게 하면 공격과 회복을 모두 같은 방식으로 차이 배열에 기록할 수 있다.
풀이 과정
1. 차이 배열 만들기
board보다 행과 열을 1칸씩 크게 만든다.
diff = [[0] * (m + 1) for _ in range(n + 1)]c2 + 1, r2 + 1 위치에 접근해야 하기 때문이다.
2. 각 스킬을 차이 배열에 기록
각 스킬에 대해 네 꼭짓점만 갱신한다.
diff[r1][c1] += degree
diff[r1][c2 + 1] -= degree
diff[r2 + 1][c1] -= degree
diff[r2 + 1][c2 + 1] += degree3. 행 방향 누적합
각 행에서 왼쪽에서 오른쪽으로 누적합을 구한다.
for i in range(n):
for j in range(m):
diff[i][j + 1] += diff[i][j]4. 열 방향 누적합
각 열에서 위에서 아래로 누적합을 구한다.
for j in range(m):
for i in range(n):
diff[i + 1][j] += diff[i][j]5. 최종 내구도 확인
각 칸의 최종 내구도는 다음과 같다.
board[i][j] + diff[i][j]이 값이 1 이상이면 파괴되지 않은 건물이다.
Python 코드
def solution(board, skill):
n = len(board)
m = len(board[0])
diff = [[0] * (m + 1) for _ in range(n + 1)]
for skill_type, r1, c1, r2, c2, degree in skill:
if skill_type == 1:
degree = -degree
diff[r1][c1] += degree
diff[r1][c2 + 1] -= degree
diff[r2 + 1][c1] -= degree
diff[r2 + 1][c2 + 1] += degree
for i in range(n):
for j in range(m):
diff[i][j + 1] += diff[i][j]
for j in range(m):
for i in range(n):
diff[i + 1][j] += diff[i][j]
answer = 0
for i in range(n):
for j in range(m):
if board[i][j] + diff[i][j] > 0:
answer += 1
return answer코드 설명
차이 배열 크기
diff = [[0] * (m + 1) for _ in range(n + 1)]직사각형 갱신에서 r2 + 1, c2 + 1을 사용하기 때문에 원래 배열보다 한 칸 크게 만든다.
공격 처리
if skill_type == 1:
degree = -degree공격은 내구도를 감소시키므로 음수로 바꾼다.
회복은 그대로 양수로 둔다.
네 꼭짓점 갱신
diff[r1][c1] += degree
diff[r1][c2 + 1] -= degree
diff[r2 + 1][c1] -= degree
diff[r2 + 1][c2 + 1] += degree이 네 곳만 갱신하면 나중에 누적합을 통해 직사각형 전체에 값이 반영된다.
행 방향 누적합
for i in range(n):
for j in range(m):
diff[i][j + 1] += diff[i][j]왼쪽에서 오른쪽으로 누적하면서 각 행에 적용될 값을 퍼뜨린다.
열 방향 누적합
for j in range(m):
for i in range(n):
diff[i + 1][j] += diff[i][j]위에서 아래로 누적하면서 최종적으로 각 칸에 적용될 변화량을 만든다.
파괴되지 않은 건물 세기
if board[i][j] + diff[i][j] > 0:
answer += 1최종 내구도가 1 이상이면 파괴되지 않은 건물이다.
문제 조건상 내구도가 0 이하이면 파괴된 것으로 본다.
왜 효율적인가?
각 스킬을 적용할 때 직사각형 내부를 전부 순회하지 않는다.
스킬 하나당 네 곳만 갱신한다.
따라서 스킬 처리 비용은 다음과 같다.
O(skill 개수)마지막에 누적합을 한 번 계산하고 전체 보드를 확인하면 된다.
시간 복잡도
보드 크기를 N x M, 스킬 개수를 K라고 하자.
O(K + N * M)스킬마다 직사각형 내부를 직접 갱신하는 방식보다 훨씬 효율적이다.
공간 복잡도
차이 배열을 추가로 사용한다.
O(N * M)정리
이 문제는 직사각형 범위 갱신이 매우 많이 일어나는 문제다.
핵심은 다음과 같다.
- 스킬마다 직사각형 전체를 직접 갱신하지 않는다.
- 2차원 차이 배열에 네 꼭짓점만 기록한다.
- 행 방향, 열 방향 누적합으로 실제 변화량을 복원한다.
- 최종 내구도가 1 이상인 칸을 센다.
2차원 누적합을 사용하면 정확성과 효율성을 모두 만족할 수 있다.
