[백준 7569번] 토마토 (python)

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

기록

(graph 3일차) 방금 전에 풀었던 7576번 토마토 문제에서 차원의 개수가 늘어났다. 똑같이 풀었더니 시간초과 뜨길래 이것저것 찾아봤더니, 전역변수보다 지역변수 호출이 더 빨라서 함수로 구현하면 해결할 수 있다는 것을 알게됐다. (pypy3로 하면 시간초과 안 난다고 들었다!)

 

최단거리를 구하는 종류의 문제이기 때문에 bfs 사용해서 구현했다. 현재 단계의 토마토와 다음 이동할 토마토를 다른 배열에 저장하여, 현재 단계의 토마토를 모두 이동시키면 다음 단계의 토마토를 현재 단계의 토마토 배열에 옮기는 과정을 반복한다. 추가로, 남은 안익은 토마토 개수를 처음부터 정의하고 방문할 때마다 개수를 줄여나가 마지막에 완료 여부를 확인하도록 했다!

 

코드

import sys
input = sys.stdin.readline

m, n, h = map(int, input().split())
board = [[list(map(int, input().split())) for i in range(n)] for i in range(h)]

tomatoes = []
total = m*n*h
for i in range(h):
    for j in range(n):
        for k in range(m):
            if board[i][j][k]==1: tomatoes.append((i, j, k))
            if board[i][j][k]==-1: total-=1

def bfs(tomatoes, total):
    visit = [[[0]*m for i in range(n)] for i in range(h)]
    for i, j, k in tomatoes : visit[i][j][k] = 1
    cnt = -1
    while tomatoes:
        cnt += 1
        temp = tomatoes.copy()
        tomatoes = []
        while temp:
            z, y, x = temp.pop()
            total -= 1
            for i, j, k in [(-1,0,0), (1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]:
                if z+i>=0 and z+i<h and y+j>=0 and y+j<n and x+k>=0 and x+k<m:
                    if visit[z+i][y+j][x+k]==0 and board[z+i][y+j][x+k]==0 :
                        tomatoes.append((z+i, y+j, x+k))
                        visit[z+i][y+j][x+k] = 1
    return -1 if total else cnt

print(bfs(tomatoes, total))

1. 변수와 토마토 정보 초기화

2. 익은 토마토(출발지점)의 위치를 저장할 tomatoes 배열과, 남은 토마토 개수를 저장할 변수를 초기화한다.

3. bfs 함수는 토마토 익는 과정이 끝나고 안 익은 토마토의 개수를 반환하는 함수이다. tomatoes에서 현재 토마토를 temp에 옮기고, 토마토를 모두 꺼내서 상하좌우 토마토를 tomatoes 배열에 추가하는 과정을 반복한다. (방문할 때마다 total-1, 한 단계 이동할 때마다 cnt-1)

4. 더 이상 익을 수 있는 토마토가 없으면 남은 토마토 개수에 따라 -1 혹은 cnt를 출력한다.