파이썬 백준 알고리즘 - 토마토 7569

안녕하세요! 개발자 여러분들을 위한 알고리즘 풀이 포스트입니다. 오늘은 백준 온라인 저지의 "토마토" 문제를 다루어 보려고 합니다. 이 문제는 3차원 상자에 익은 토마토를 퍼뜨리는 과정을 시뮬레이션하는 문제입니다. 코드를 통해 자세히 알아보도록 하겠습니다.

문제 내용

주어진 상자에는 토마토가 들어있고, 일부 토마토는 익어있습니다. 익은 토마토는 주변의 안 익은 토마토를 익힐 수 있습니다. 이때, 토마토가 모두 익을 때까지 걸리는 최소 일수를 구하는 문제입니다. 단, 상자의 크기와 토마토의 초기 상태가 주어집니다.

 

문제 이해하기

주어진 코드를 살펴보면, 주어진 3차원 상자의 크기와 초기 상태를 입력받습니다. 그리고 BFS(Breadth-First Search) 알고리즘을 사용하여 토마토를 익히는 과정을 구현합니다. 익은 토마토의 위치를 큐에 저장하고, 큐가 빌 때까지 토마토를 하나씩 꺼내면서 인접한 안 익은 토마토를 익힙니다. 이 과정을 반복하여 모든 토마토가 익을 때까지 진행합니다. 각 토마토의 익는 날짜는 이전 토마토의 익는 날짜에 1을 더한 값으로 갱신됩니다.

 

풀이 코드

pythonCopy code
import sys
from collections import deque

input = sys.stdin.readline

# -1 토마토 없음 / 0 안 익은 토마토 / 1 익은 토마토

# 위, 아래, 상, 하, 좌, 우
dz = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, 0, 0, -1, 1]
dx = [0, 0, -1, 1, 0, 0]

def bfs():
  while queue:
    z, y, x = queue.popleft()

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

      if nz < 0 or ny < 0 or nx < 0 or nz >= h or ny >= n or nx >= m:
        continue

      if dimen_3[nz][ny][nx] == -1:
        continue

      if dimen_3[nz][ny][nx] == 0:
        queue.append((nz, ny, nx))
        dimen_3[nz][ny][nx] = dimen_3[z][y][x] + 1

m, n, h = map(int, input().split())

def get_min_day():
  max_day = -1

  for z in range(h):
    for y in range(n):
      for x in range(m):
        if dimen_3[z][y][x] == 0:
          return -1

        if dimen_3[z][y][x] > max_day:
          max_day = dimen_3[z][y][x]

  if max_day == 1:
    return 0

  return max_day - 1

dimen_3 = []
queue = deque([])

for z in range(h):
  dimen_2 = []
  for y in range(n):
    dimen_1 = list(map(int, input().split()))
    for x in range(m):
      if dimen_1[x] == 1:
        queue.append((z, y, x))
    dimen_2.append(dimen_1)
  dimen_3.append(dimen_2)

bfs()
print(get_min_day())

풀이 방법

주어진 코드는 BFS 알고리즘을 사용하여 토마토를 익히는 과정을 구현하고 있습니다. 코드의 주요 로직은 다음과 같습니다.

1. 주어진 입력에서 3차원 상자의 크기와 초기 상태를 받아옵니다.
2. BFS를 위해 큐를 생성하고, 초기 익은 토마토의 위치를 큐에 추가합니다.
3. 큐가 빌 때까지 다음 과정을 반복합니다.
   • 큐에서 토마토의 위치를 꺼냅니다.
   • 해당 위치에서 상, 하, 좌, 우, 위, 아래 방향의 토마토를 확인하고, 안 익은 토마토라면 큐에 추가하고 익힌 날짜를 기록합니다.
4. 모든 토마토가 익은 후에는 익힌 날짜를 검사하여 최소 일수를 반환합니다.

위의 방법으로 주어진 3차원 상자의 토마토를 익히는 과정을 구현하고 최소 일수를 구할 수 있습니다.

 

시간 복잡도

이 문제의 시간 복잡도는 주어진 상자의 크기에 따라 선형적으로 증가합니다. 주어진 상자의 크기를 H, N, M이라고 할 때, 토마토가 있는 모든 위치를 확인하는 데는 O(H * N * M)의 시간이 걸립니다. 따라서, 이 문제의 시간 복잡도는 O(H * N * M)입니다.

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음