[프로그래머스] 파괴되지 않은 건물 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
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개의 건물이 파괴되지 않았습니다.

---

이 문제는 22년도 카카오 블라인드 채용 당시 직접 경험했던 문제다.

당시에는 갑작스러운 취업 준비로 인해 1주일 정도 밖에 공부하지 못했었고, 그래프 탐색, 최단경로, 누적합 등의 개념을 몰랐기에 전체 배열을 탐색하는 방법으로 밖에 시도해보지 못했다.

 

그리고 채용과정에 불합격한 후에 꾸준하게 코딩 테스트를 준비하다가 다시 만나게 되었다.

 

처음에는 이 전과 같이 2차원 배열을 skill 하나씩 탐색하며 board를 탐색하는 브루트포스 코드를 작성했었다.

(그리고 마치 맞춘것 마냥 이 문제가 level 3이 맞나 생각했었다.)

 

아주 순조롭게 정확성 테스트 케이스를 전부 통과하고..

효율성 테스트 케이스를 전부 시간초과 해버렸다..

 

<틀린 코드 보기>

def solution(board, skill):
    answer = len(board) * len(board[0])

    for s in skill:
        if s[0] == 1:
            for i in range(s[1], s[3]+1):
                for j in range(s[2], s[4]+1):
                    flag = board[i][j] > 0 #원래는 정상적인 건물
                    board[i][j] -= s[5]
                    if flag and board[i][j] <= 0: # 공격받고 파괴되었는가 검사
                        answer -= 1
        else:
            for i in range(s[1], s[3]+1):
                for j in range(s[2], s[4]+1):
                    flag = board[i][j] <= 0 #원래 파괴된 건물
                    board[i][j] += s[5]
                    if flag and board[i][j] > 0: #회복받고 복구되었는가 검사
                        answer += 1
        
    
    return answer

제한 조건 중에 

• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000

라는 조건이 있었기에 board 전체를 한번 더 탐색하지 않고 flag를 통해 접근하려는 앙큼한 생각이었지만, 문제는 skill 안에 있었다.

 

극단적인 예시로 board가 1,000*1,000일 때 skill의 길이가 최대인 250,000이고, 모든 skill의 원소가 항상 board 전체 범위를 타격할 때, 1,000*1,000의 범위를 250,000번이나 반복해서 연산하게 되므로 시간초과가 발생했다.

(시간 복잡도 O(N * M * K))

 

사실 처음에는 해결 방법을 찾지 못하고 열심히 서핑하였다.

그러다 카카오 팀에서 직접 밝힌 접근법에서 O(K + N * M)의 시간에 문제를 풀 수 있다고 했고, 그 방법의 중심에는 '누적합'의 개념이 있었다.

(카카오 팀의 접근법 링크)

(누적합 개념 링크)

 

이 전까지는 한번도 사용해보지 않았던 알고리즘이라 생소하기도 하고 설명을 보아도 무슨 말인지 정확하게 이해 못하고 이게 왜 더 빠르지? 라는 의문도 가졌었다.

 

하지만 직접 작성해보고 테스트를 진행해보니 점차 이해가 갔고 결국에는 정답을 맞출 수 있었다.

 

<정답 코드>

def solution(board, skill):
    answer = 0
    tmp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
    
    for type, r1, c1, r2, c2, degree in skill:
        tmp[r1][c1] += degree if type == 2 else -degree
        tmp[r1][c2 + 1] += -degree if type == 2 else degree
        tmp[r2 + 1][c1] += -degree if type == 2 else degree
        tmp[r2 + 1][c2 + 1] += degree if type == 2 else -degree

    for x in range(len(tmp) - 1):
        for y in range(len(tmp[0]) - 1):
            tmp[x][y + 1] += tmp[x][y]

    for y in range(len(tmp[0]) - 1):
        for x in range(len(tmp) - 1):
            tmp[x + 1][y] += tmp[x][y]

    for x in range(len(board)):
        for y in range(len(board[0])):
            board[x][y] += tmp[x][y]
            if board[x][y] > 0: 
                answer += 1
                
    return answer

작성된 코드에 반복문이 너무 많이 보여 지저분하고 더 복잡해 보일 수 있지만, 해당 코드를 통해 문제를 접근하게 되면 항상 board 전체를 2번만 순회하게 되면 정답을 도출할 수 있다.

 

접근 방법은 아래와 같다.

1. board보다 행,열로 한 칸씩 더 큰 2차원 누적합 기록 배열을 생성한다.
2. skill을 순회하면서 하나의 skill이 나타내는 사각형의 꼭짓점(우측과 하단으론 한칸씩 더 증가시킨다)에 degree를 기록한다. (자세한 것은 누적합의 개념을 숙지해야 이해할 수 있다.)
3. 기록된 누적합 배열의 행, 열 기준으로 누적합을 계산한다.
4. 누적합 배열과 기존 board를 더해주면서 파괴되지 않은 건물의 수를 계산한다. 

문제를 푸는 것에만 집중하면 쉬워보일 수 있는 문제였으나, 효율성을 고려하게 되면서 굉장히 어려워졌던 문제이다.

 

그리고 누적합의 설명은 보통 1차원 배열을 예시로 들기 때문에 개념을 이해하는데 어려움이 있었다.

 

그래도 고생 끝에 문제를 해결했기 때문에 오래 기억에 남을 것 같다.

 

---

내가 이해한 2차원 누적합 개념 간단 설명

기존 배열이 5*5라고 가정하고 진행한다.

 

그렇게 되면 누적합 배열은 6*6이 되고 최초의 모습은 아래 사진과 같다.

 

이 상태에서 [0, 0]과 [1, 1]의 사각형이 들어왔다고 하자. 그렇다면 우리는 아래와 같이 기록해야한다.

우리가 원하는 것은 [0, 0]부터 [1, 1]까지 전부 1이 되는 그림이기 때문에 이렇게 기록해야 한다.

 

바로 누적합을 계산해서 결과를 확인해보자.

 

처음에는 행을 기준으로 누적합을 진행한다.

행을 기준으로 j+1번째 칸의 값이 현재 값에 j번째 칸의 값을 더한 값이 되므로 위와 같이 진행되었고, [0, 2]가 -1일 때 [0, 1]의 1과 더해지면서 0이 된 후는 전부 0+0이 된다.

(편의를 위해 0이 아닌 칸에 대해서만 진행했다.)

최종적으로 진행된 결과 값이 두 번째 사진처럼 된다.

 

이러한 원리로 또 열을 기준으로 합을 진행해보면,

최종적으로 이와 같이 나타나게 된다.

이렇게 되면 우리가 원했던 [0, 0], [1, 1]을 꼭짓점으로 가지는 사각형 만큼 값을 삽입하게 된 것이다.

 

이렇게 계산된 누적합 배열을 기존 board 배열에 더하게 되면 우리가 원하는 값이 도출될 것이다.

 

이렇게 문제를 푸는 것이 항상 빠르게 작용하는 것은 아니나, 브루트포스로 풀었을 때 예시를 든 것 같은 경우에는 이것이 훨씬 빨리 작동할 수 있다.