BOJ 7576 토마토(Python 3)

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

재미있는 BFS문제이다.

완전 탐색으로 1이 들어간 값을 전부 큐에 저장한 뒤에 BFS 돌리면 된다.

이 문제에서 질문 글이 쏟아지는데 파이썬은 최댓값을 제대로 잡았는지, 방문 체크 리스트를 만들어서 이미 방문한 곳인지 아닌지 확인하면 된다.

코드확인

from collections import deque
dx,dy=[0,0,1,-1],[1,-1,0,0]
m,n=map(int,input().split())
D=[[*map(int,input().split())] for _ in range(n)]
a=[[-1]*m for _ in range(n)]
q=deque()
for i in range(n):
    for j in range(m):
        if D[i][j]==1:
            a[i][j]=0
            q.append((i,j))
while q:
    x,y=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if D[nx][ny]==0 and a[nx][ny]==-1:
                q.append((nx,ny))
                a[nx][ny]=a[x][y]+1
ans=max([max(row) for row in a])
for i in range(n):
    for j in range(m):
        if D[i][j]==0 and a[i][j]==-1:
            ans=-1
print(ans)