[伯俊]7569:トマト

質問する

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

悩みの部分

一度に一人のノードを連れて行って、東西南北の上下を世話する方法を考えました.
->最初に1として入力した座標をリストに入れ、1の値を持つすべての座標をリストに入れます!
そして、bfsを1回ループした後、変更値を含むリストをパラメータとしてbfsに戻り続けます!

結果:タイムアウト(Python)、メモリタイムアウト(PyPy)

改善すべき点:1をキューに一度に入れ、キューに値がなくなるまでbfsを返すにはどうすればいいですか?

解決策queueにはすべてのものが入っています

->トマトを入力すると、いっそ一人の座標値は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)