[백준 7569] 토마토

1. 문제

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

7569번: 토마토

2. 접근 방법

bfs로 풀면 됩니다

 

여기서는 가로, 세로 뿐만 아니라 높이도 고려해야하기 때문에

이에 맞춰서 direction을 6개로 만들어주면 됩니다

 

그리고 초기 상태에서 아직 익지 않은 토마토의 갯수를 세서, 

익은 토마토를 사용해 토마토를 익혀주다가

토마토가 더 이상 익지 않는 경우 -> 토마토가 다 익어서 안익는 건지, 혹은 다 못익히는 건지 판단 후 print를 합니다

그리고 토마토가 다 익었을 경우 걸린 시간을 print해줍니다.

3. 코드

python

from collections import deque
import sys


def grow_tomato():
    global ok_tomato, adj
    ok_tomato_len = len(ok_tomato)
    change_cnt = 0
    for _ in range(ok_tomato_len):
        nx, ny, nh = ok_tomato.popleft()
        for i in range(6):
            tx, ty, th = nx + adj[i][0], ny + adj[i][1], nh + adj[i][2]
            if 0 <= tx < M and 0 <= ty < N and 0 <= th < H and tomatoes[th][ty][tx] == 0:
                change_cnt += 1
                tomatoes[th][ty][tx] = 1
                ok_tomato.append((tx, ty, th))
    return change_cnt


M, N, H = map(int, sys.stdin.readline().split())
tomatoes = [[list(map(int, sys.stdin.readline().split())) for _ in range(N)] for _ in range(H)]

ok_tomato = deque()
adj = [(0, 0, -1), (0, 0, 1), (1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0)]
answer = 0
is_answer = False
yet_tomato = 0

for h in range(H):
    for y in range(N):
        for x in range(M):
            if tomatoes[h][y][x] == 1:
                ok_tomato.append((x, y, h))
            elif tomatoes[h][y][x] == 0:
                yet_tomato += 1

while yet_tomato > 0:
    change_cnt = grow_tomato()
    yet_tomato -= change_cnt
    if change_cnt == 0 and yet_tomato > 0:
        is_answer = True
        print(-1)
        break
    answer += 1

if not is_answer:
    print(answer)

4. 마치며

dict에 빠져서 

아직 익지 않은 토마토를 dict로 표현하다가 시간초과, 메모리 초과 하다가

인절미 크로플 먹고 정신 차렸습니다.