[백준/Python] 16931 : 겉넓이 구하기

 

이 문제는 3차원 격자 구조물의 겉넓이를 구하는 문제이다.

2차원 배열이 처음에 주어지는데 여기서 각 칸의 값은 해당 위치에 쌓인 블록의 높이를 나타냄

어려워 보여도 겉넓이의 성질을 이해하면 풀 수 있다.

 

- 정육면체로 이루어져 있기 때문에, 해당 문제에서 겉넓이는 6면 모두 구할 필요 없이 왼쪽 오른쪽 아래쪽 이렇게 3면만 구한 뒤에 2배를 하면 된다.

- 그런데 여기서 지금 바닥면인 base는 N*M으로 이미 주어져있기 때문에 사실상 두 개의 면만 구하면 끝!

- 이를 쉽게 이해하려면 정사영 투영을 떠올리면 쉬움

 

import sys
N, M = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

base = N * M

left = 0
for i in range(N):
    for j in range(M):
        if j == 0:
            left += arr[i][j]
        else:
            if arr[i][j-1] < arr[i][j]:
                left += arr[i][j] - arr[i][j-1]

front = 0
for j in range(M):
    for i in range(N):
        if i == 0:
            front += arr[i][j]
        else:
            if arr[i-1][j] < arr[i][j]:
                front += arr[i][j] - arr[i-1][j]
        
answer = 2 * (base + left + front)
print(answer)

 

arr 배열은 각 위치에 해당하는 블록의 높이를 저장한다.

앞서 언급했듯 여기서는 left와 right만 구하면 끝나는데, 둘의 원리는 동일하다.

 

왼쪽 면인 left로 설명해보자면, 일단 if문 첫 번째 열에서 무조건 arr[i][0] 만큼의 면적이 추가되는데, 이는 첫 열에서 보이는 블록의 왼쪽 면이다.

그리고 그 후에 현재 칸의 블록 높이인 arr[i][j]가 이전 칸의 높이 arr[i][j-1]보다 클 때만 면적을 추가하며, 이때 추가되는 면적은 두 칸의 높이 차이이다. 즉, arr[i][j] - arr[i][j-1]만큼 왼쪽에서 보이는 면적이 새로 생기는 것!

 

같은 원리로 right 면도 구한 다음 마지막으로 3면을 합쳐서 2배 해준 값을 출력하면 정답이다.

 

 

++ 보면 비슷한 구조가 두 번 나와서 다음과 같이 함수로 축약할 수도 있다.

다만 행렬을 뒤집어서 전치된 배열처럼 처리하기 위해 transpose 인자를 추가하여 코드를 수정하면 된다.

 

import sys
N, M = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def calculate_side(area, rows, cols, transpose=False):
    total = 0
    for i in range(rows):
        for j in range(cols):
            # 배열을 전치해서 계산할 경우
            current = area[j][i] if transpose else area[i][j]
            
            # 첫 번째 열 또는 행인 경우 무조건 블록 높이만큼 추가
            if j == 0:
                total += current
            else:
                # 이전 열 또는 행의 값과 비교하여 추가
                previous = area[j-1][i] if transpose else area[i][j-1]
                if previous < current:
                    total += current - previous
    return total

base = N * M

# 왼쪽(열 기준)과 앞쪽(행 기준) 계산을 하나의 함수로 처리
left = calculate_side(arr, N, M)  # 열 기준(왼쪽)
front = calculate_side(arr, M, N, transpose=True)  # 행 기준(앞쪽)

answer = 2 * (base + left + front)
print(answer)