[Python] 프로그래머스 > 파괴되지 않은 건물

ssu_hong·2022년 3월 1일
2

2022 KAKAO BLIND RECRUITMENT 에서 6번 문제로 나왔던 '파괴되지 않은 건물'입니다.

파괴되지 않은 건물

문제 설명

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

효율성 테스트 제한사항

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

입출력 예

boardskillresult
[[5,5,5,5,5], [5,5,5,5,5], [5,5,5,5,5], [5,5,5,5,5]][[1,0,0,3,4,4], [1,2,0,2,3,2], [2,1,0,3,1,2], [1,0,1,3,3,1]]10
[[1,2,3], [4,5,6], [7,8,9]][[1,1,1,2,2,4], [1,0,0,1,1,2], [2,2,0,2,0,100]]6

문제풀이

누적합 알고리즘을 알고리즘을 확장한 IMOS법을 사용하여 해결하였습니다.
기존에 모든 index에 가중치를 입력함으로써 생기는 반복을 IMOS법은 시작과 종료만을 기록함으로써 크게 줄일 수 있습니다. 입력마다 시작지점에 가중치를 더하고, 종료지점에 반대 부호의 가중치를 더합니다. 그 후, 배열의 누적합을 계산하면 각각 인덱스의 가중치를 구할 수 있게 됩니다.

각 입력 i (0 ≤ i < C) 당 시작지점 S와 종료지점 E가(0 ≤ S < E ≤ T) 주어졌다고 했을 때,
나이브한 방식으로는, 각각의 입력이 속한 각 지점의 가중치 더하는 방법을 들 수 있습니다. 이 방식은 시간복잡도가 O(CT)입니다.

IMOS법의 경우 입력당 시작지점, 종료지점만 기록을 하기 때문에 시간복잡도가 입력의 개수 C와 누적합을 계산하는 시뮬레이션 T를 더한 값 즉, O(C+T)입니다.

광고 삽입 / 2021 KAKAO BLIND RECRUITMENT (1차원 형태의 IMOS법 문제)

1차원의 경우 위의 방식을 그대로 적용하면 되지만, 2차원의 경우 행 기준 누적합과 열 기준 누적합을 모두 구해야하기 때문에 네 지점의 좌표에 기록을 해야합니다.
누적합 계산을 완료한 후 생성된 배열과 board를 더해 몇 개의 건물이 파괴되지 않았는지 카운트하면 해결이 됩니다.

IMOS법에 자세한 설명(삼각형 등 특수 좌표계로의 확장 등)

def skillCheck(s_map, skill):
    for action in skill:
        r1 = action[1]; c1 = action[2]; r2 = action[3]; c2 = action[4]
        degree = action[5]
       
        if action[0] == 1: # attack
            s_map[r1][c1] -= degree
            s_map[r1][c2+1] += degree
            s_map[r2+1][c1] += degree
            s_map[r2+1][c2+1] -= degree
        else: # restore
            s_map[r1][c1] += degree
            s_map[r1][c2+1] -= degree
            s_map[r2+1][c1] -= degree
            s_map[r2+1][c2+1] += degree
   
    for r in range(n+1): # 행 기준 누적합
        for c in range(1, m+1):
            s_map[r][c] += s_map[r][c-1]
           
    for c in range(m+1): # 열 기준 누적합
        for r in range(1, n+1):
            s_map[r][c] += s_map[r-1][c]      
    return
           
def solution(board, skill):
    global n, m
    n = len(board); m = len(board[0])
    s_map = [[0]*(m+1) for _ in range(n+1)]
    skillCheck(s_map, skill)
   
    answer = 0
    for r in range(n):
        for c in range(m):
            if s_map[r][c] + board[r][c] > 0:
                answer += 1
               
    return answer
profile
프론트엔드에 관심이 많은 프린이입니다!

0개의 댓글