[백준] 7569 : 토마토

문제

https://www.acmicpc.net/problem/7569

고민했던 부분

• 1인 노드들을 어떻게 한번에 가져가서 동서남북상하를 봐줘야 하는 건지 고민했음
  -> 처음에 입력받았을 때 1인 것의 좌표를 넣는 리스트에 1 값을 가진 것들의 좌표를 모두 넣어줌!
  그리고 bfs가 한 번 돌고 난 이후엔 변경된 값들을 담은 리스트를 매개변수로 해서 bfs를 계속 돌려줌!

• 결과 : 시간 초과(Python), 메모리 초과(PyPy)

• 개선해야 하는 부분 : 어떻게 1을 한번에 넣어주고 queue에 더이상 값이 없을 때까지 bfs를 돌려줄 수 있을까??

• 해결책

  queue에 모든 것들을 담아서 처리해준다

-> 토마토들을 입력받을 때 아예 1인 것들은 좌표값을 queue에 append 해줌!
-> 그리고 나중에 변해야 하는 것들은 queue에 또 append 해줌!
-> 결과적으로 queue엔 1인 좌표 값들이 먼저 pop으로 처리되면서 계속 변해야 하는 부분이 뒤에 쌓이는 구조가 됨
-> 1인 좌표 값이 먼저 그래프를 변화시키고, 그 다음에 변화되어야 하는 부분이 기준이 되어야 하므로 그 다음에 큐에서 처리되는 구조!

시간초과 풀이

from collections import deque
import sys
input = sys.stdin.readline

# 의문 1. visited 처리를 해줘야 하나? - no no

M, N, H = map(int, input().split())
box = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]

# 좌표 이동
dx = [-1, +1, 0, 0, 0, 0]
dy = [0, 0, -1, +1, 0 ,0]
dz = [0, 0, 0, 0, -1, +1]

ok = 0 # 익은 토마토 개수 1 
notyet = 0 # 익지 않은 토마토 개수 0
nothing = 0 # 아무것도 없는 토마토 개수 -1

onelist = []
for i in range(H):
    for j in range(N):
            num = list(map(int, input().split()))
            ok += num.count(1)
            notyet += num.count(0)
            nothing += num.count(-1)
            box[i][j] = num

total = M * N * H

# 저장될 때부터 모든 토마토가 익어있는 상태인 경우 0 출력
if total == (ok + nothing):
    print(0)
    exit(0)

# 1인 것의 좌표를 넣는 리스트
onelist = []
for a in range(H):
    for b in range(N):
        for c in range(M):
            if box[a][b][c] == 1:
                onelist.append((a, b, c))
                
# BFS 함수
def bfs(onelist):
    queue = deque()
    
    # 1로 만들어줘야 하는 좌표 리스트
    clist = []
    
    for d, e, f in onelist: # 1인 것들의 좌표
        queue.append((d, e, f))
        
        while queue:
            z, y, x = queue.popleft()
            exist = box[z][y][x]
          
            for k in range(6):
                p, l, m =  z + dz[k], y + dy[k], x + dx[k] # 이동했을 때 좌표 (층  H, 열 N, 행 M)
                if 0 <= p <= H-1 and 0 <= l <= N-1 and 0 <= m <= M-1: # 범위 안에 들 때
                    
                    if box[p][l][m] == 0:
                        clist.append((p, l, m))
                       

    for q, w, e in clist:
        box[q][w][e] = exist + 1
    
    if len(clist) == 0:
        print(-1)
        exit(0)
    
    for g in range(H):
        for h in range(N):
            if box[g][h].count(0) >= 1:
                bfs(clist)
    

# 1인 좌표의 리스트를 넣고 너비 우선 탐색
bfs(onelist)

maxNum = -1

for a in range(H):
    for b in range(N):
        for c in range(M):
            maxNum = max(maxNum, box[a][b][c])

print(maxNum-1)

제대로 된 풀이

import sys
from collections import deque
M,N,H = map(int,input().split()) # mn크기, h상자수

queue = deque([])
 
graph = [] 
for i in range(H):
    tmp = []
    for j in range(N):
        tmp.append(list(map(int,sys.stdin.readline().split())))
        for k in range(M):
            if tmp[j][k]==1:
                queue.append([i,j,k]) # 큐에 1인 것들을 넣어주면 먼저 처리됨!
    graph.append(tmp)

dx = [-1,1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]

while(queue):
    x,y,z = queue.popleft()
    
    for i in range(6):
        a = x+dx[i]
        b = y+dy[i]
        c = z+dz[i]
        if 0<=a<H and 0<=b<N and 0<=c<M and graph[a][b][c]==0:
            queue.append([a,b,c])
            graph[a][b][c] = graph[x][y][z]+1                   # 원래 1이었던 애들 주변을 2로만든다. 2었던 애들이 0인 애들을 익게하면 3으로만들고...
            
day = 0
for i in graph:                 # level
    for j in i:                 # row
        for k in j:             # column
            if k==0:
                print(-1)       # while문이 끝나도 0인애가 있다면 -1 출력
                exit(0)
        day = max(day,max(j))   # 가장 나중에 익은 과일의 수를 불러옴
print(day-1)