[ProblemSolving] 백준 7576번 토마토 문제풀이

아직 많은 문제를 접해보지는 않았지만 BFS, DFS 탐색을 사용하는 문제들이 재미있다. 그래서 오늘도 그래프 탐색을 사용한 '토마토' 문제를 가져왔다. 문제 해설은 링크를 확인해주기 바랍니다.

 

백준 7576번 토마토 문제 해설

7576번: 토마토

해당 문제는 익은 토마토가 위치한 부분 전부를 큐에 우선 넣어준 후에 BFS 탐색을 실행시키는 방식으로 해결이 가능하다. 과정은 다음과 같다. 토마토의 정보를 가지고 있는 배열은 data라고 하겠다.

 

• data에서 익은 토마토의 위치를 탐색한다.
• 익은 토마토의 위치를 큐에 넣어준다. 
• 익은 토마토의 위치가 모두 들어갈 때까지 1의 과정을 반복한다.
• BFS를 실행한다.
• data에서 0인 값이 있다면 -1을 반환한다.
• 아니라면 가장 큰 값을 반환해준다.

위의 과정을 코드로 작성하면 다음과 같다.

 

from collections import deque
 
def checkData():
  answer = 0
  for i in range(m):
    for j in range(n):
      if data[i][j] == 0:
        return -1
      else:
        answer = max(answer, data[i][j])
  return answer-1
 
def bfs(queue):
  dx = [-1, 0, 1, 0]
  dy = [0, -1, 0, 1]
  
  while queue:
    x, y = queue.popleft()
 
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
 
      if nx >= 0 and nx < m and ny >= 0 and ny < n:
        if not visited[nx][ny] and data[nx][ny] != -1:
          data[nx][ny] = data[x][y] + 1
          queue.append((nx, ny))
          visited[nx][ny] = True
 
n, m = map(int, input().split())
data = []
visited = [[False] * n for _ in range(m)]
 
for _ in range(m):
  data.append(list(map(int, input().split())))
 
queue = deque()
 
for i in range(m):
  for j in range(n):
    if data[i][j] == 1:
      queue.append((i, j))
      visited[i][j] = True
 
bfs(queue)
print(checkData())

 

토마토 문제는 BFS를 사용해야 할 위치를 모두 넣어준 후에 실행하는 것에서 다른 BFS 문제와 차이가 있었던 것 같다.