17086 아기상어2

ylab 2023. 3. 7. 11:08

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

17086번: 아기 상어 2

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만

www.acmicpc.net

from collections import deque
n,m = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
    
#상어 있는 곳에서 가장 가까운 상어까지 거리 구하면됨
#그 구한 거리중에서 가장 작은거 구하면됨    

#상하좌우 상우 상좌 하우 하좌
dx=[-1,1,0,0,-1,-1,1,1]
dy=[0,0,-1,1,-1,1,1,-1]


q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] ==1:
            
            q.append((i,j))
    


def bfs():
    global ans
    while q:
        x,y = q.popleft()
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            #safe+=1
            #범위 안에 있고, 상어가 없다면
            if 0<=nx<n and 0<=ny<m: 
                if graph[nx][ny]==0:
                    q.append((nx,ny))
                    graph[nx][ny] = graph[x][y]+1
                    ans = max(ans,graph[nx][ny])
                
ans=0            
bfs()
print(ans-1)