백준_7576_토마토(python)

 예전에 한 번 풀었었는데 스터디로 인해 한번 더 풀게 됐다. 한번 풀어보기도 했고 간단한 탐색 문제였기에 자신있게 풀었지만 92%에서 틀렸다고 나왔다. 알고리즘적으로 틀릴 이유가 없다고 생각해서 많이 헤맸다.

 

풀이

익은 토마토들을 한 번에 영향력을 주기 때문에 처음에 1이 어디있었는지 다 찾아서 deque에다가 넣는다.

그 다음에 순서대로 하나씩 꺼내어 주변 익지 않은 토마토가 있다면 현재 좌표에서 +1을 해서 토마토를 익게 해주고 이제 이 토마토도 deque에 넣는다.

 

헤맸던 지점

if flag == 1:이라는 조건을 한번 더 체크해줬어야 했는데 누락시켰다.  옜날이었으면 이런데서 실수하지 않고 오히려 구현을 못했을 텐데 반대가 됐다. 세세한 부분도 신경을 쓰는 습관을 들여야겠다.

from collections import deque

m,n = map(int,input().split())

data = [list(map(int,input().split())) for _ in range(n)]

tomato = deque()

dx = [-1,1,0,0]
dy = [0,0,-1,1]

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


for i in range(n):
    for j in range(m):
        if data[i][j] == 1:
            tomato.append((i,j))

bfs(data,tomato)
result = max(map(max,data))
flag = 0
for i in range(n):
    for j in range(m):
        if data[i][j] == 0:
            flag = 1
            print(-1)
            break
    if flag == 1:
        break
if flag == 0:
    print(result - 1)