[백준/Python] 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

from collections import deque

m, n = map(int, input().split()) # 가로, 세로
graph = [list(map(int, input().split())) for _ in range(n)] # 토마토 정보
# 동서남북 이동 방향
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
queue = deque()
answer = 0 # 토마토가 모두 익을 최소 날짜

# 익은 토마토만 큐에 담기
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

# BFS 수행
def bfs():
      while queue:
          x, y = queue.popleft()
          for i in range(4):
              xi = x + dx[i]
              yi = y + dy[i]
              if xi <= -1 or xi >= n or yi <= -1 or yi >= m:
                  continue
              if graph[xi][yi] == 0:
                  queue.append([xi, yi])
                  graph[xi][yi] = graph[x][y] + 1

bfs()
# 토마토가 모두 익을 최소 날짜 구하기
for g in graph:
    for v in g:
        if v == 0:
            print(-1)
            exit(0)
    answer = max(answer, max(g))
print(answer - 1) # 1부터 시작했으므로 -1 해준다

이 문제는 BFS 문제로 DFS로는 풀리지 않는 문제였다. 처음에 DFS로 했다가 안풀려서 코드 갈아엎음....

 

1.  상자의 가로, 세로 크기와 토마토 정보를 입력받는다.

2. 토마토가 익을 최소 날짜를 구해야하기 때문에 익은 토마토만 먼저 큐에 담는다.

3. 모든 토마토가 익을 때까지 BFS를 수행한다.

    3-1. 큐에서 익은 토마토 하나를 가져온다.

    3-2. 해당 토마토의 동서남북 방향에 있는 토마토 위치를 구한다.

    3-3. 토마토 위치가 상자 범위를 넘어가면 다음 토마토로 넘어간다.

    3-4. 토마토가 익지 않은 상태라면 큐에 추가하고 토마토 상태를 변경한다. (이 때, 해당 토마토 상태에 +1 하여 토마토가 익을 날짜를 구하도록 한다.)

4. 토마토가 모두 익을 최소 날짜를 구한다. 0이 존재하면 토마토가 익지 못하는 상황이므로 -1를 출력한다.

5. 최소 날짜를 출력한다. 1부터 시작했으므로 -1 해준다.