문제 개요
N×M 크기의 2차원 행렬 A가 하나의 3D(입체) 도형을 나타낸다고 가정해 보겠습니다. 이때 좌표 (i, j) 위치에 있는 기둥의 높이는 A[i][j] 값입니다. 우리가 구해야 하는 것은 이 입체 도형의 전체 표면적입니다.
예를 들어 입력이 N = 3, M = 3, A = [[1, 4, 5], [3, 3, 4], [1, 3, 5]]라고 한다면, 출력 결과는 72가 됩니다.
해결 접근 방식
표면적을 계산하는 핵심 아이디어는 다음 세 가지로 정리할 수 있습니다.
- 윗면과 아랫면: 모든 격자 칸에는 윗면과 바닥면이 하나씩 존재하므로, 이 두 면의 넓이는 항상 N × M × 2로 고정됩니다.
- 인접 칸 사이의 옆면: 인접한 칸과의 높이 차이만큼 옆면이 노출됩니다. 따라서 현재 칸과 위쪽·왼쪽 칸의 높이 차이 절댓값을 누적하면 됩니다.
- 외곽 경계면: 행렬의 마지막 행과 마지막 열에 있는 칸은 바깥쪽으로 노출된 면이 있으므로, 해당 칸의 높이만큼 면적을 추가로 더해 줍니다.
이를 알고리즘 단계로 표현하면 다음과 같습니다.
- 결과 변수
res를 0으로 초기화합니다. - i를 0부터 N−1까지, j를 0부터 M−1까지 이중 반복문으로 순회합니다.
up_side와left_side를 0으로 초기화합니다.- i > 0이면
up_side = array[i-1][j], j > 0이면left_side = array[i][j-1]로 설정합니다. res에 |array[i][j] − up_side| + |array[i][j] − left_side|를 더합니다.- i가 마지막 행(N−1)이면
res에 array[i][j]를 더합니다. - j가 마지막 열(M−1)이면
res에 array[i][j]를 더합니다. - 모든 반복이 끝나면
res에 N × M × 2를 더하고 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 과정을 확인해 보겠습니다.
M = 3
N = 3
def get_surface_area(array):
res = 0
for i in range(N):
for j in range(M):
up_side = 0
left_side = 0
if (i > 0):
up_side = array[i - 1][j]
if (j > 0):
left_side = array[i][j - 1]
res += abs(array[i][j] - up_side) + abs(array[i][j] - left_side)
if (i == N - 1):
res += array[i][j]
if (j == M - 1):
res += array[i][j]
res += N * M * 2
return res
array = [[1, 4, 5], [3, 3, 4], [1, 3, 5]]
print(get_surface_area(array))
실행 결과
입력
[[1, 4, 5], [3, 3, 4], [1, 3, 5]]
출력
72
결과 검증
위 예제에서 결과가 72가 되는 이유를 분해해 보면 다음과 같습니다.
- 윗면 + 아랫면: 3 × 3 × 2 = 18
- 노출된 옆면 전체(높이 차이 + 외곽 경계면): 54
- 총 표면적: 18 + 54 = 72
이 방식은 각 칸을 한 번씩만 방문하므로 시간 복잡도가 O(N×M)으로 매우 효율적입니다. 행렬의 크기가 커져도 선형 시간 안에 표면적을 계산할 수 있다는 점이 이 알고리즘의 가장 큰 장점입니다.