[python] 백준 - 7576 (토마토)

2025.12.31ko 0 시리즈 · 알고리즘 #알고리즘

골드5 문제이며, 제한 시간은 1초이다.

문제

해결 과정

일단 척 봐도 BFS 문제였다. 생각한 아이디어는 BFS를 이용하며 1인 곳을 큐에 넣고 돌린다. 방문 처리를 날짜 계산으로 활용할 수 있도록 한다. 최종적으로 visited 리스트의 값이 0이면서, 그래프의 값이 -1이 아니면 토마토가 익지 않았다는 뜻이므로 -1 출력하고, 그렇지 않다면 모든 토마토가 익었다는 뜻이므로 visited의 max값 출력한다.

나는 맨 처음에 익은 토마토가 들어있던 곳을 또 방문하지 않기 위해 값을 1로 시작했으며, 그렇기에 출력할 때 -1을 해서 출력한다.

풀이

from collections import deque

def bfs():
  queue = deque()
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1:
        queue.append((i, j))
        visited[i][j] = 1

  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0 and visited[nx][ny] == 0:
        visited[nx][ny] = visited[x][y] + 1
        queue.append((nx, ny))


m, n = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[0 for _ in range(m)] for _ in range(n)]

bfs()

flag = False
for i in range(n):
  if flag:
    break
  for j in range(m):
    if visited[i][j] == 0 and graph[i][j] != -1:
      flag = True
      break

ans = max(max(row) for row in visited)

if flag:
  print(-1)
else:
  print(ans - 1)

어렵지 않은 문제였다!

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기