[백준 7569] 토마토 (Gold 5)

문제

[백준] 토마토 (Gold 5)

요약

익은 토마토의 상/하/좌/우/위/아래 방향에 있는 익지 않은 토마토는 하루 뒤에 익은 토마토가 된다.
모든 익지 않은 토마토가 익은 토마토가 되는 데 걸리는 최소 일수를 구하자.
만약 토마토가 모두 익지 못하는 상황이면 -1을 출력하자.

풀이

1. BFS

q에 초기에 주어진 1의 인덱스를 넣는다.
bfs 탐색을 시작한다.
일수를 세기 위해 또 다른 예비 리스트 t 를 만든다. q가 다 비면 t를 q에 복사하고 비워준다.

<배운 것들>

deque 와 list는 용도에 따라 구분해서 사용해야 한다.
- deque : 큐를 다룰 때, 양쪽에서 삭제 및 삽입 가능 (저장 : O(1), 조회 : O(n))
- list : 빈번한 조회가 이루어질 때 (저장 : O(1) ~ O(n), 조회 : O(1))
더 좋은 풀이.. 링크

from collections import deque
import sys

# m : 가로(col), n : 세로(row), h: 높이
m, n, h = map(int, sys.stdin.readline().split())
arr = [[list(map(int,
                 sys.stdin.readline().split())) for _ in range(n)]
       for _ in range(h)]

dz, dy, dx = [0, 0, 0, 0, 1, -1], [0, 1, 0, -1, 0, 0], [1, 0, -1, 0, 0,
                                                        0]  # 동남서북 위아래

for i in range(h):
  for j in range(n):
    for k in range(m):
      if arr[i][j][k] == 1:
        q.append([i, j, k])

q = deque()
t = []
ans = 0
while q:
  z, y, x = q.popleft()

  for i in range(6):
    nz, ny, nx = z + dz[i], y + dy[i], x + dx[i]

    if 0 <= nz < h and 0 <= ny < n and 0 <= nx < m and arr[nz][ny][nx] == 0:
      t.append([nz, ny, nx])
      arr[nz][ny][nx] = 1

  if not q and t:
    q = deque(t)
    t = []
    ans += 1

for floor in arr:
  for row in floor:
    if 0 in row:
      ans = -1
      break

print(ans)

[백준 7569] 토마토 (Gold 5)

문제

요약

분류

풀이

1. BFS