[백준_17086]_아기상어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은 아기 상어가 있는 칸이다. 빈칸의 개수가 한 개 이상인 입력만 주어진다.

출력

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

문제 해결

n*m크기의 격자에 아기 상어는 대각선 포함 상하좌우 총 8방향으로 이동이 가능하다. 문제에서 말하는 안전거리를 쉽게 말하면 상어가 격자 위 (x, y) 위치에 있을 때 graph [nx][ny]까지의 최단거리를 의미한다. 예제 1에서 아기 상어가 (5,1)에 위치해있을 때 (3,1)까지의 거리인 2가 안전거리인 셈이다. 

문제는 2가지 방법으로 해결 가능하다.

첫 번째는 각 좌표마다 너비 우선 탐색인 bfs를 하여 상어와의 최단거리를 구하는 것이다. n과 m의 크기가 50 이하이기 때문에 시간 복잡도상 O(N^4)이 가능하다.

두 번째는 기준점을 상어로 바꾸어 상어의 위치를 que에 넣고 너비 우선 탐색을 하여 visited방문처리 배열에 depth를 넣어주어 방문 처리해준다. 그 visited배열에서의 가장 큰 값이 안전거리의 최댓값이기에 map함수를 사용하여 최댓값을 구해주면 된다.

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

def bfs():
    while que:
        dx,dy,k = que.popleft()
        for i in range(8):
            nx,ny = dx+dxs[i],dy+dys[i]
            if in_range(nx,ny) and not visited[nx][ny] :
                visited[nx][ny] = visited[dx][dy]+1
                que.append((nx,ny,k+1))

def in_range(x, y):
    return 0 <= x < r and 0 <= y < c

r , c = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(r)]
visited = [[0]*c for _ in range(r)]
dxs,dys = [-1,-1,-1,0,0,1,1,1],[-1,0,1,-1,1,-1,1,0]
que = deque()

for i in range(r):
    for j in range(c):
        if graph[i][j]:
            que.append((i,j,0))
            visited[i][j] = 1
bfs()
print(max(map(max,visited))-1)