[백준] 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

제출 답안

• 각 칸마다 아기 상어를 제외하고 도달 하기 위한 횟수를 증가한다.
• 대각선도 방문해야 하니 dy, dx에 대각선 위치도 추가한다.
• 마지막에 1을 빼는 이유는 상어가 1인데 1부터 누적하였기에 1을 뺀다.

'''
1. 아이디어
- 상어에서 해당 칸 까지의 거리를 계속 업데이트
2. 시간 복잡도
- O(v+E)
- v = NM
- e = 4v
= 5(50*50) = 500 < 2억
3. 자료구조
int [][]
'''

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
graph = []
q = deque()
for i in range(n):
    row = list(map(int, input().split()))
    for idx, j in enumerate(row):
        if j == 1:
            # 여기서 미리 아기 상어 위치를 q에 담는다.
            q.append((i, idx))
    graph.append(row)

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

def bfs():
    while q:
        y, x = q.popleft()
        for k in range(8):
            ny = y + dy[k]
            nx = x + dx[k]
            if 0<=ny<n and 0<=nx<m:
                if graph[ny][nx] == 0:
                    q.append((ny, nx))
                    graph[ny][nx] = graph[y][x] + 1
    return

bfs()
answer = 0
for row in graph:
    answer = max(answer, max(row))

print(answer - 1)