[Python/BOJ] 17086. 아기 상어 2

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

17086번: 아기 상어 2

문제

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

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

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

입력

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

출력

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

풀이

Code

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

# 1. bfs 함수 선언
def bfs(x, y) :
    # 1-1. 큐에 현재 위치 삽입
    queue = deque()
    queue.append((x, y, 0))
    # 1-2. 방문 여부 리스트 생성
    visited = [[False] * m for _ in range(n)]
    # 1-3. 방문 처리
    visited[x][y] = True
    # 1-4.
    while queue :
        # 1-4-1. 위치 인덱스 반환
        x, y, count = queue.popleft()
        # 1-4-2.
        for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)] :
            # 다음 위치 설정
            nx, ny = x + dir_x, y + dir_y
            # 예외 처리
            if nx < 0 or nx >= n or ny < 0 or ny >= m : continue
            # 해당 위치 도달 최솟값 업데이트
            if not visited[nx][ny] and graph[nx][ny] == 0 :
                visited[nx][ny] = True
                distance[nx][ny] = min(distance[nx][ny], count + 1)
                queue.append((nx, ny, count + 1))
    return
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
distance = [[sys.maxsize] * m for _ in range(n)]
# 2. 상어 위치 인덱스 추출
sharks = []
for i in range(n) :
    for j in range(m) :
        if graph[i][j] : sharks.append([i, j])
# 3.
for i, j in sharks :
    # 3-1. bfs 실행
    bfs(i, j)

# 4. 결과 출력
ans = -sys.maxsize
for i in range(n) :
    for j in range(m) :
        if distance[i][j] != sys.maxsize :
            ans = max(ans, distance[i][j])
print(ans)