[알고리즘] 파괴되지 않은 건물 python(프로그래머스)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

 

누적합을 활용한 파괴되지 않은 건물 문제 해설

1. 문제 해결 접근 방식: 2차원 누적합

이 문제의 핵심은 2차원 배열에서의 누적합(prefix sum) 기법을 활용하는 것입니다. 일반적인 브루트포스 방식으로 접근하면 시간 복잡도가 매우 높아져 효율적인 해결이 불가능합니다.

 

누적합을 활용한 파괴되지 않은 건물 문제 해설

 

1. 스킬의 영향력 이해하기

예를 들어 다음과 같은 3x4 보드가 있다고 가정해보겠습니다:

[
    [5, 5, 5, 5],
    [5, 5, 5, 5],
    [5, 5, 5, 5]
]

그리고 다음과 같은 스킬이 있다고 해봅시다:

skill = [type=1, r1=1, c1=1, r2=2, c2=2, degree=4]
# type=1은 공격을 의미하며, (1,1)부터 (2,2)까지의 영역에 4만큼의 데미지를 줍니다.

스킬 적용 과정 시각화

 

1) 전통적인 방식 (비효율적)

# 직접 각 칸에 데미지를 적용
[
    [5,  5,  5, 5],
    [5,  1,  1, 5],  # (1,1)부터 (2,2)까지
    [5,  1,  1, 5]   # 4만큼 감소
]

2) 누적합 방식 (효율적)
먼저 한 칸 더 큰 sBoard를 만듭니다 (4x5):

[
    [0,  0,  0,  0, 0],
    [0,  0,  0,  0, 0],
    [0,  0,  0,  0, 0],
    [0,  0,  0,  0, 0]
]

그리고 다음과 같이 값을 기록합니다:

# sBoard에 영향력 기록
[
    [0,   0,   0,   0, 0],
    [0,  -4,   0,   4, 0],  # (1,1)에 -4, (1,3)에 4
    [0,   0,   0,   0, 0],
    [0,   4,   0,  -4, 0]   # (3,1)에 4, (3,3)에 -4
]

 

왜 이렇게 기록하나요?

이것은 마치 "도장 찍기"와 같은 개념입니다:

1. 시작점 (r1,c1)에 -4를 기록: 이 지점부터 영향이 시작됩니다.
2. 오른쪽 경계 (r1,c2+1)에 +4를 기록: 이 지점 이후로는 영향이 없어져야 합니다.
3. 아래쪽 경계 (r2+1,c1)에 +4를 기록: 이 지점 아래로는 영향이 없어져야 합니다.
4. 대각선 지점 (r2+1,c2+1)에 -4를 기록: 중복 계산을 방지합니다.

 

이렇게 기록한 후 누적합을 계산하면:

# 최종 누적합 계산 결과
[
    [0,  0,  0,  0],
    [0, -4, -4,  0],
    [0, -4, -4,  0]
]

이 결과를 원본 보드와 더하면 우리가 원하는 결과가 나옵니다:

    [5,  5,  5, 5]     [5,  5,  5, 5]
    [5,  1,  1, 5]  =  [5, -4, -4, 5]  +  원본 보드
    [5,  1,  1, 5]     [5, -4, -4, 5]

이 방식의 장점은:

1. 각 스킬 적용시 4개의 지점만 수정하면 됩니다 (영역 크기와 무관)
2. 마지막에 한 번의 누적합 계산으로 모든 결과를 얻을 수 있습니다

 

2. 누적합 계산 과정

각 칸의 최종 값은 다음과 같이 계산됩니다:

• 현재 칸 = 현재 값 + 위쪽 누적합 + 왼쪽 누적합 - 왼쪽 위 대각선 누적합

이는 마치 2차원 배열에서 직사각형 영역의 합을 구하는 것과 같은 원리입니다.

 

3. 코드 상세 설명

def solution(board, skill):
    # 누적합을 기록할 배열 생성 (원본 배열보다 가로,세로 각각 1칸 크게 생성)
    sBoard = list(map(lambda x: [0] * (len(board[0]) + 1), range(len(board) + 1)))

    # 각 스킬의 영향력을 경계점에 기록
    for (type, r1, c1, r2, c2, degree) in skill:
        # type이 1이면 공격(-), 2면 회복(+)
        degreeValue = degree * (1 if type == 2 else -1)

        # 영역의 시작점에 값을 더함
        sBoard[r1][c1] += degreeValue
        # 영역의 오른쪽 경계선에 값을 뺌
        sBoard[r1][c2 + 1] -= degreeValue
        # 영역의 아래쪽 경계선에 값을 뺌
        sBoard[r2 + 1][c1] -= degreeValue
        # 영역의 대각선 지점에 값을 더함 (중복 제거)
        sBoard[r2 + 1][c2 + 1] += degreeValue

    # 누적합을 계산할 결과 배열 생성
    resBoard = list(map(lambda _: [0] * len(sBoard[0]), range(len(sBoard))))
    answer = 0

    # 2차원 누적합 계산
    for row in range(len(board)):
        for col in range(len(board[0])):
            cur = sBoard[row][col]  # 현재 위치의 값

            # 위쪽 누적합 더하기
            if row > 0:
                cur += resBoard[row - 1][col]
            # 왼쪽 누적합 더하기
            if col > 0:
                cur += resBoard[row][col - 1]
            # 중복 계산된 왼쪽 위 대각선 값 빼기
            if row > 0 and col > 0:
                cur -= resBoard[row - 1][col - 1]

            resBoard[row][col] = cur  # 현재 위치의 최종 누적합 저장
            # 원본 배열값과 누적합을 더해서 양수면 카운트
            answer += 1 if (resBoard[row][col] + board[row][col]) > 0 else 0

    return answer

 

3. 시간 복잡도 분석

• 기존 방식: O(skill의 개수 × 영향 받는 칸의 개수)
• 누적합 방식: O(skill의 개수 + board의 크기)

누적합을 사용하면 각 스킬의 영향력을 기록하는데 O(1)의 시간이 걸리고, 최종 계산은 board를 한 번만 순회하면 되므로 훨씬 효율적입니다.