[BOJ 17086🥈2] 아기 상어 2 (Python)

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

17086번: 아기 상어 2

문제

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

 

⭕ CODE

from collections import deque

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

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

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

min_result = 1000

q = deque()

# 아기 상어가 존재하는곳 q에 담아준다
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            q.append((i,j))

max_result = 0

while q:
    x,y = q.popleft()
	
    # 8방향에 대해서
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
		
        # 격자 안에 존재하고 빈칸이라면
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] == 0:
            	# 1칸 진행했으므로 업데이트
                arr[nx][ny] = arr[x][y] + 1
                q.append((nx,ny))
                # 가장 먼 거리를 재기위한 비교
                max_result = max(max_result,arr[nx][ny])

# 시작값이 1이였으므로 최대거리에서 1 빼주기
print(max_result-1)

✏️ Comment

bfs를 사용하여 문제를 풀었고 처음에는 빈칸을 기준으로 문제를 풀까 고민했지만 상어를 기준으로 문제를 푸는것이 더 효율적일거같아서 상어를 기준으로 잡았다.