아기 상어2 - 백준 #17086, 그래프/브루트포스 알고리즘/너비 우선 탐색

문제

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

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

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

입력

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

출력

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

예제

입력	출력
5 4 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1	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

풀이

N,M = map(int, input().split())
sharks = []	# 상어의 위치를 저장할 리스트
for i in range(N):
    row = list(map(int, input().split()))
    for j, exist in enumerate(row):
        if exist == 1:
            sharks.append((i, j))

result = -1e9
for i in range(N):
    for j in range(M):
        minDist = 1e9
        for x, y in sharks:
            # 상어와의 최단거리 구하기
            distance = max(abs(i-x), abs(j-y))
            minDist = min(distance, minDist)
        # 모든 최단 거리 중 최대 안전거리 구하기 
        result = max(minDist, result)

print(result)