[알고리즘] 백준 17086 파이썬 - 아기 상어 2

 

17086번: 아기 상어 2

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

 

 

문제풀이

from collections import deque
n,m=map(int,input().split())
graph=[]
q=deque()
for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(m):
    	#01
        if tmp[j]==1:
            q.append((i,j))
    graph.append(tmp)

def bfs():
	#02
    dx=[-1,1,0,0,-1,1,-1,1]
    dy=[0,0,-1,1,1,-1,-1,1]
    while q:
        x,y=q.popleft()
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny]==0:
                    q.append((nx,ny))
                    graph[nx][ny]=graph[x][y]+1
    return
#03
bfs()
ans=0
#04
for i in range(n):
    for j in range(m):
        ans=max(graph[i][j],ans)
print(ans-1)

- #01 : q에는 공간의 값이 1인 것들의 좌표를 미리 저장해놓는다.

- #02 : dx,dy는 근접 8방향으로 움직일 수 있는 좌표를 정의해놓은 것이다.

           while문과 for문을 통해 nx,ny의 값을 변화를 주면서,

           특정 조건에 맞다면 q에 추가하고, 이동하기 전의 값 +1 값을 해당 좌표에 저장한다.

- #03 : bfs를 실행하면 초기 q에 있는 좌표들을 모두 popleft할 때까지 반복된다.

           즉 1 좌표를 기준으로 그 주변 안전거리를 graph에 기록하는 것이다.

           계속해서 그 주변 좌표가 0이라면 q에 추가하고 값을 1씩 늘려가며 거리를 측정한다.

- #04 : ans 값에는 모든 graph 값을 돌며, 가장 큰 값을 ans에 저장한다.

           이후 [x][y]의 초기값이 1이기에, ans에서 -1한 값을 출력해준다.