[백준 16931] 겉넓이 구하기 (Python)

 

 

최근에 수학학원에서 애기들을 가르쳤던 내용이 비슷하게 문제로 나와서 신기했다.

맨날 애기들 블록 개수랑 층 별로 블록 모양이 뭔지 가르치는데 내가 틀릴 수는 없지 ! 하고 문제를 풀기 시작했다.

 

문제를 보면 블록의 겉넓이를 구해야 하는데 한번에 모든 겉넓이를 구하는 것은 어렵겠다는 생각이 들었다.

그래서 1층, 2층,... 이렇게 층별로 나눈뒤에 각층의 옆 넓이를 구하고 윝 넓이, 밑넓이를 더해주는 방식으로 풀고자 한다.

참고로 밑넓이와 윗넓이는 둘 다 n*m으로 동일하다.

 

코드

from collections import deque
n, m = map(int, input().split())

blocks = []
max_floar = 0
for _ in range(n):
    a = list(map(int, input().split()))
    blocks.append(a)
    if max(a) > max_floar:
        max_floar = max(a)

def solution(n, m, blocks, max_floar):
    result = n * m * 2
    direct = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for floar in range(1, max_floar + 1):
        visited = [[0 for i in range(m)] for j in range(n)]
        for x in range(n):
            for y in range(m):
                if blocks[x][y] >= floar and visited[x][y] == 0:
                    area, visited = bfs(blocks, floar, direct, visited, x, y)
                    result += area

    return result


def bfs(blocks, floar, direct, visited, x, y):
    queue = deque([(x, y)])
    visited[x][y] = 1
    area = 0
    while queue:
        curr_x, curr_y = queue.popleft()
        
        for a, b in direct:
            next_x = curr_x + a
            next_y = curr_y + b
            if  0 > next_x or next_x >= n or 0 > next_y or next_y >= m :
                area += 1
            elif blocks[next_x][next_y] < floar:
                area += 1
            elif visited[next_x][next_y] == 0:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = 1
    #print(area, floar)
    return area, visited

print(solution(n, m, blocks, max_floar))

이 문제는 너무 어렵게 생각하면 안되는 것 같다.

 

각 칸에 놓인 정육면체의 수를 입력 받을 때 최고 층수값을 max_floar에 넣는다.

 

그리고 각 층에서 블록이 존재하는 칸이 나오면 bfs 함수를 호출하여 해당 블록과 연결되어 있는 모든 블록들이 갖는 겉넓이를 구한다. 

여기서 겉넓이를 구할 때 현재 블록의 상하좌우를 조사하는데 범위를 벗어나거나 층이 더 낮다면 다른 블록과 맞대고 있는 면이 아니기 때문에 겉넓이를 +1 해주었다.