[Problem Solving] 백준 7569번 토마토 문제풀이

백준 7569번 토마토 문제풀이에 대해서 알아보겠습니다. 문제 해설은 다음의 링크를 참고해주시기 바랍니다. 문제 해설

 

토마토 문제는 그래프 탐색 문제입니다. 따라서 bfs를 사용하여 구현해야 합니다. 해결 방법은 다음과 같습니다.

 

1. 처음 박스에 존재하는 토마토의 위치를 저장한다.
2. 지정한 범위에 벗어나지 않은 안 익은 토마토를 찾아서 도달한 시간을 저장한다.
3. 박스의 정보를 순차적 탐색하여 0이 존재하는지 확인한다. (5. 0이 존재한다, 6. 0이 존재하지 않는다.)
4. -1을 출력한다.
5. 도달한 시간의 최대값에서 1을 뺀 값을 출력한다.

위의 과정에서 도달한 시간이란 처음 토마토에서 시작하여 해당 위치까지 몇 번의 탐색 끝에 왔는지를 나타냅니다. 다음은 해결 방법에 따라 구현한 코드입니다.

 

# 백준 No.7569 토마토
from collections import deque

def bfs():
  dx = [-1, 0, 1, 0, 0, 0]
  dy = [0, -1, 0, 1, 0, 0]
  dz = [0, 0, 0, 0, -1, 1]

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

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

      if nx < n and nx >= 0 and ny < m and ny >= 0 and nz < h and nz >= 0:
        if not visited[nz][ny][nx] and data[nz][ny][nx] == 0:
          queue.append((nx,ny,nz))
          data[nz][ny][nx] = data[z][y][x] + 1
          visited[nz][ny][nx] = True

n, m, h = map(int, input().split(' '))
data = []
queue = deque()
answer, count = 0, 0
isExist0 = True

for _ in range(h):
  temp = []
  for _ in range(m):
    line = list(map(int, input().split(' ')))
    temp.append(line)
  data.append(temp)

visited = []
for _ in range(h):
  visited.append([[False] * n for _ in range(m)])

for z in range(h):
  for y in range(m):
    for x in range(n):
      if data[z][y][x] == 1:
        visited[z][y][x] = True
        queue.append((x, y, z))
bfs()

for z in range(h):
  for y in range(m):
    for x in range(n):
      if data[z][y][x] == 0:
        isExist0 = False
      answer = max(answer, data[z][y][x])

if isExist0:
  print(answer-1)
else:
  print(-1)

 

코드를 확인해보면 토마토 문제는 다른 bfs 탐색과는 다른 특징을 가지고 있습니다. 특징은 다음과 같습니다.

 

1. 상, 하, 좌, 우, 위, 아래 총 6가지의 움직임을 가지고 있다.
2. 토마토가 존재하는 곳은 모두 동시에 주변 토마토에 영향을 주어야 한다.

기존에는 2차원을 사용하여 4가지 방향으로 탐색하는 것이 많았는데 토마토 문제는 3차원을 사용하기 때문에 6가지 방향의 움직임을 가지고 있습니다. 따라서 다음과 같이 구현하는 것으로 문제를 해결하였습니다. 다음은 해결 코드입니다.

 

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

 

다음은 2번입니다. 동시에 주변 토마토에 영향을 주기 위해서는 bfs를 실행하기 전에 큐에 먼저 초기 토마토들의 값을 넣어주어 순서에 맞게 bfs가 실행되도록 하는 것으로 해결할 수 있습니다. 다음은 해결 코드입니다.

 

for z in range(h):
  for y in range(m):
    for x in range(n):
      if data[z][y][x] == 1:
        visited[z][y][x] = True
        queue.append((x, y, z))

 

지금까지의 bfs 문제는 2차원에서 해결했었던 것에 비해 토마토 문제는 3차원을 사용한다는 것에서 새로운 유형의 문제였습니다.