[python]7576번 토마토, 시작점이 여러 개인 BFS

시작점이 여러개여서 당황했다. 시작점 하나가 다 돌아간다면, 이미 그래프 탐색은 끝나기에 나머지 시작점들을 사용할 수 없었다. 따라서 시작점 하나하나를 순서대로 처리하는것이 아닌 동시에 처리해야했다.

 

그래서 큐 대기열에 만족하는 시작점들을 바로 넣었다.

이때 반례로

2 2
0 0
0 0

이와 같은 반례가 있어, 시작점이 없을 경우도 생각해야했다.

import sys
from collections import deque
input = sys.stdin.readline
clmn,row = map(int,input().split())
stg = []
for i in range(row):
    stg.append(list(map(int,input().split())))
visit = [[0 for i in range(clmn)]for j in range(row)]
newx = [0,0,-1,1]
newy = [1,-1,0,0]
def bfs(list):
    que = deque()
    for i in list:
        que.append((i[0],i[1],i[2]))       #시작점들을 큐 대기열에 집어넣기
    while que:
        cur = que.popleft()
        get = cur[2]       #최소 횟수 저장
        for i in range(4):
            x = cur[1]+newx[i]
            y = cur[0]+newy[i]
            if 0<=x<clmn and 0<=y<row and not visit[y][x] and stg[y][x]==0:
                stg[y][x] = 1    #토마토가 익었다
                visit[y][x] =1  
                que.append((y,x,cur[2]+1))  #대기열에 옆의 안 익은 토마토 위치 추가
    return get
rst = 0
ready = []
for i in range(row):       #시작점들을 다 탐색하는 과정
    for j in range(clmn):
        if stg[i][j]==1 and not visit[i][j]:
            visit[i][j] = 1
            ready.append((i,j,0)) 
if ready:   #시작점이 있다면, 만약 없다면 BFS에 넣을 리스트값이 없어 조건문을 달았다
    rst+= bfs(ready)
for i in range(row):         #안 익은 토마토 있는지 탐색하는 과정
    for j in range(clmn):
        if not stg[i][j]:
            print(-1)
            exit(0)
print(rst)

 

 

 

 

 

tworiver님의 풀이

from collections import deque
M, N = map(int, input().split())

box = []
for _ in range(N):
  box.append(list(map(int, input().split())))

q = deque([])
for i in range(N):
  for j in range(M):
    if box[i][j] == 1:
      q.append((i,j))

res = 0
while q:
  x, y = q.popleft()
  pos = [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]
  for p in pos:
    if 0<=p[0]<N and 0<=p[1]<M:
      if box[p[0]][p[1]] == 0:
        box[p[0]][p[1]] = box[x][y] + 1
        res = max(res, box[p[0]][p[1]])
        q.append((p[0],p[1]))

if res!=0:
  res = res-1

for i in range(N):
  for j in range(M):
    if box[i][j]==0:
      res = -1
      break

print(res)