https://www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
기본 BFS이지만, 복수의 시작점을 가진 BFS에 대해 다시 한번 생각해보는 계기가 됐다.
from collections import deque
m, n = map(int,input().split())
graph = []
for _ in range(n) :
graph.append(list(map(int, input().split())))
dx, dy = [-1, 1, 0, 0], [0, 0, -1 ,1]
q = deque([]) # queue 생성
for i in range(n) :
for j in range(m) :
if graph[i][j] == 1 :
q.append((i, j))
def bfs():
while q :
x, y = q.popleft()
for i in range(4) :
_x, _y = x+dx[i], y+dy[i]
if 0<=_x<n and 0<=_y<m and graph[_x][_y] == 0 :
graph[_x][_y] = graph[x][y] + 1
q.append((_x, _y))
bfs()
is_done = True
res = -1
for i in range(n) :
for j in range(m) :
if graph[i][j] == 0 : # 한개라도 익지 못한 토마토가 있으면 = 토마토가 모두 익지는 못하는 상황 = -1을 출력
is_done = False
res = max(res, graph[i][j])
if is_done :
print(res-1)
else :
print(-1)
처음에는 각자 다른 시작점을 가진 BFS를 어떡하지...? 생각했는데
queue에 들어가는 순서를 유심히 생각해보니
그냥 순서대로 시작점(1)가 popleft되어도, 시작점에서 "1만큼씩만" 체크하고, 다시 다음시작점이 popleft된다.
그래서 한개의 큐만 써도 됐다. 와~!