(백준) 7576: 토마토

인접한 토마토들이 익는다고 하였으므로 BFS로 간단하게 해결 할 수 있다.

 

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

 

from collections import deque

m,n = map(int,input().split()) #n은 가로이지만 배열에서는 세로가 되고 m은 세로이지만 배열에서 가로가 된다
box = []
queue = deque()

#토마토 입력
for i in range(n):
  row = list(map(int,input().split()))
  for j in range(m):
    #토마토가 있는지 체크
    if row[j] == 1:
      queue.append((i,j))
  box.append(row)

# 상하좌우 이동을 위한 방향 벡터
dx = [0, 0, -1, 1]  # 상하좌우
dy = [-1, 1, 0, 0]  # 상하좌우

def bfs():
  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 box[nx][ny] == 0:
        queue.append((nx,ny))
        box[nx][ny] = box[x][y] + 1

bfs()

result = 0
for i in range(n):
  for j in range(m):
    if box[i][j] == 0:
      print(-1)
      exit(0)
    # 최대 일수 갱신
    result = max(result, box[i][j])

# 처음 토마토가 1이었으므로 1을 빼줌
print(result - 1)

 

주의할점은

1.이차원 배열이므로 x,y의 좌표계가 바뀌게 된다.

2.BFS는 deque로 큐를 만들어서 구한다. 인접한 노드들을 큐에 넣으면 되는 간단한 구조를 가지고 있다.

3.BFS 문제 유형은 box[nx][ny] = box[x][y] + 1 를 해주는 경우가 많은데 이는 문제를 해결하기 위해서 기록을 해두는 것이다.

예를들면 미로 찾기도 최적 경로를 계산할때 위와 같은 방법을 사용한다.