파이썬 | 백준 | 7569 | 토마토 | bfs 3차원 시간초과

solution

1. 상자의 수 H → 3차원 배열 tomatoes[z][x][y]

2. 최소 일수 → BFS

# 7569, 토마토
import sys
from collections import deque

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

def bfs(x,y,z):
    q = deque()
    q.append((x, y, z))
    visited[z][x][y] = 1
    cnt = 0
    while q:
        a, b, c = q.popleft()
        for i in range(6):
            nx = a + dx[i]
            ny = b + dy[i]
            nz = c + dz[i]
            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
                if visited[nz][nx][ny] == 0 and tomatoes[nz][nx][ny] == 0:
                    tomatoes[nz][nx][ny] = 1
                    visited[nz][nx][ny] = visited[c][a][b] + 1
                    cnt = visited[nz][nx][ny]
                    q.append((nx, ny, nz))
    return cnt-1

# 모두 익어있는지 확인 0이 있으면 안 익은 토마토 -> return 0
# 0이 없으면 모두 익은 토마토 -> return 1
def find1():
    for z in range(h):
        for x in range(n):
            for y in range(m):
                if tomatoes[z][x][y] == 0:
                    return 0
    return 1

m, n, h = map(int, sys.stdin.readline().split())
tomatoes = [[[] for _ in range(n)] for __ in range(h)]
for i in range(h):
    for j in range(n):
        tomatoes[i][j].extend(list(map(int, sys.stdin.readline().split())))



visited = [[[0]*m for _ in range(n)] for __ in range(h)]

max_ = 0
for z in range(h):
    for x in range(n):
        for y in range(m):
            if tomatoes[z][x][y] == 1:
                max_ = max(max_, bfs(x, y, z))
# 안 익은 토마토 있으면 -1 출력
if not find1():
    print(-1)
else:
    print(max_)

시간 초과

---

deque에 토마토가 있는 좌표를 모두 추가한 후 bfs() 호출

# 7569, 토마토
import sys
from collections import deque

dx = (-1, 1, 0, 0, 0, 0)
dy = (0, 0, -1, 1, 0, 0)
dz = (0, 0, 0, 0, -1, 1)

def bfs():
    while q:
        a, b, c = q.popleft()
        visited[c][a][b] = 1
        for i in range(6):
            nx = a + dx[i]
            ny = b + dy[i]
            nz = c + dz[i]
            if 0 <= nx < n and 0 <= ny < m and 0 <= nz < h:
                if visited[nz][nx][ny] == 0 and tomatoes[nz][nx][ny] == 0:
                    tomatoes[nz][nx][ny] = tomatoes[c][a][b] + 1
                    visited[nz][nx][ny] = 1
                    q.append((nx, ny, nz))


m, n, h = map(int, sys.stdin.readline().split())
tomatoes = [[[] for _ in range(n)] for __ in range(h)]
for i in range(h):
    for j in range(n):
        tomatoes[i][j].extend(list(map(int, sys.stdin.readline().split())))

visited = [[[0]*m for _ in range(n)] for __ in range(h)]

q = deque()

for z in range(h):
    for x in range(n):
        for y in range(m):
            if tomatoes[z][x][y] == 1:
                q.append((x, y, z))

bfs()

max_ = 0
for z in range(h):
    for x in range(n):
        for y in range(m):
            if tomatoes[z][x][y] == 0:
                print(-1)
                sys.exit()
            else:
                max_ = max(max_, tomatoes[z][x][y])
print(max_-1)

57756KB
4312ms

 

문제 출처 https://www.acmicpc.net/problem/7569

7569번: 토마토