문제 개요
N×N 크기의 격자 위에 1×1×1 크기의 정육면체를 쌓는 상황을 생각해 봅시다. 각 격자 칸의 값 v = grid[i][j]는 해당 위치 (i, j) 위에 쌓인 정육면체의 개수, 즉 기둥(탑)의 높이를 의미합니다. 이렇게 만들어진 전체 입체 도형의 표면적(surface area)을 구하는 것이 목표입니다.
예를 들어 입력이 [[1,2],[3,4]]라면 결과값은 34가 됩니다.
접근 방법
이 문제의 핵심은 인접한 기둥끼리 맞닿아 숨겨지는 면을 빼 주는 것입니다. 전체 표면적은 다음 세 부분으로 나누어 생각할 수 있습니다.
- 윗면과 아랫면: 높이가 1 이상인 칸마다 위·아래 면이 하나씩 노출되므로, 0이 아닌 칸의 개수 × 2가 됩니다.
- 옆면: 각 칸의 기둥은 자신의 높이만큼 네 방향으로 옆면을 가지므로, 모든 값의 합 × 4가 됩니다.
- 숨겨지는 면: 인접한 두 기둥의 높이가 h1, h2일 때, 서로 마주 보는 면 중 낮은 높이만큼은 외부에 보이지 않습니다. 따라서
2 × min(h1, h2)만큼 차감해야 합니다.
이를 알고리즘으로 정리하면 다음과 같습니다.
adjacentArea()함수를 정의합니다. 한 줄(행 또는 열)을 입력받아 인접한 두 값 사이에 숨겨지는 면적을 계산합니다.area = 0으로 초기화합니다.- 인접한 두 값이 모두 0이 아니면
area += 2 × min(row[i], row[i+1])을 더합니다. - 모든 인접 쌍을 확인한 뒤
area를 반환합니다.
- 메인 메서드에서는 다음 값을 계산합니다.
z: 각 행에서 0보다 큰 값의 개수를 모두 더한 뒤 2를 곱한 값 (윗면 + 아랫면)x_plus_y: 격자의 모든 요소 합에 4를 곱한 값 (전체 옆면)x_adjacent: 모든 행에 대해adjacentArea()를 적용한 값의 합 (행 방향 숨겨진 면)y_adjacent: 모든 열에 대해adjacentArea()를 적용한 값의 합 (열 방향 숨겨진 면)
- 최종 답은
z + (x_plus_y − x_adjacent − y_adjacent)입니다.
구현 예제
class Solution:
def surfaceArea(self, grid):
def adjacentArea(row):
area = 0
for i in range(len(row) - 1):
if row[i] and row[i + 1]:
area += 2 * min(row[i], row[i+1])
return area
z = sum([sum(i > 0 for i in row) for row in grid]) * 2
x_plus_y = sum([sum(row) for row in grid]) * 4
x_adjacent = sum([adjacentArea(row) for row in grid])
y_adjacent = sum([adjacentArea(row) for row in zip(*grid)])
return z + (x_plus_y - x_adjacent - y_adjacent)
ob = Solution()
print(ob.surfaceArea([[1,2],[3,4]]))
참고로 zip(*grid)는 격자의 행과 열을 뒤바꾸어(transpose) 주므로, 같은 함수를 재사용해 열 방향의 인접 면도 손쉽게 계산할 수 있습니다.
입력 및 실행 결과
입력
[[1,2],[3,4]]
출력
34
예제로 살펴보는 동작 원리
입력 [[1,2],[3,4]]가 어떻게 34가 되는지 단계별로 확인해 보겠습니다.
- 0이 아닌 칸은 4개이므로
z = 4 × 2 = 8 - 모든 값의 합은 10이므로
x_plus_y = 10 × 4 = 40 - 행 방향: [1, 2]에서 2×min(1,2)=2, [3, 4]에서 2×min(3,4)=6 →
x_adjacent = 8 - 열 방향: [1, 3]에서 2×min(1,3)=2, [2, 4]에서 2×min(2,4)=4 →
y_adjacent = 6 - 최종 결과:
8 + (40 − 8 − 6) = 34
시간 복잡도
격자의 모든 칸을 상수 번씩만 방문하면 되므로 시간 복잡도는 O(N²)이며, 추가로 사용하는 공간은 열을 생성하는 zip(*grid) 정도로 O(N) 수준입니다. 격자 기반의 기하 문제 중에서도 매우 효율적인 풀이에 속합니다.