[BOJ] 17086 아기상어2 (Python3)

문제

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

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

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

입력

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

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

예제 입력 1
5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1
예제 출력 1
2

예제 입력 2
7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1
예제 출력 2
2

문제풀이

bfs 문제인데, 다른 문제들과 다르게 4방향이 아닌 대각선을 포함한 8방향으로 이동할 수 있다는게 특이한 문제이다. 다른 문제들과 마찬가지로 bfs로 풀이하면 되지만
dx와 dy를 8개의 요소를 갖는 리스트로 선언해주고 모든 좌표를 방문하다가 상어가 있는 좌표에 도달하면 bfs함수를 불러와 다름 1이 나올때까지 이동하며 그 이동거리를 누적하여 더해준 후, 가장 큰 안전거리 값을 출력한다.

코드

from collections import deque
def bfs():
    while q:
        x,y = q.popleft()
        for k in range(8):
            nx,ny = x + dx[k], y + dy[k]
            if nx < 0 or nx>=n or ny <0 or ny >=m:
                continue
            if space[nx][ny] == 0:
                q.append([nx,ny])
                space[nx][ny] = space[x][y] + 1
        
#공간의 크기 n,m
n,m = map(int,input().split())

q = deque()

#공간의 모습 
space = []
for i in range(n):
    space.append(list(map(int, input().split())))
    for j in range(m):
        if space[i][j] == 1:
            q.append([i,j])
            

#대각선 이동하기 위한 dx, dy
dx = [1,-1,0,0,1,-1,1,-1]
dy = [0,0,1,-1,1,-1,-1,1]


bfs()
dist = 0
for i in range(n):
    for j in range(m):
        dist = max(space[i][j], dist)
        
print(dist-1)

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1
3