[백준 17086] 아기 상어 2

https://www.acmicpc.net/problem/17086 문제이해 NxM 크기의 공간에 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다.

두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향이 가능하다. 풀이 모든 칸에 대해서 BFS를 실행해 아기 상어를 만나기까지의 가장 먼 거리를 구하는 방법으로 처음에 풀었다 연산양도 최악의 경우 6,250,000이기 때문에 충분할 거라 생각했는데 python3에서 시간 초과가 발생했다.

(pypy3는 정답) 그래서 결국 악어가 있는 칸에서 출발하는 방법을 선택했고 이 방법이 메모리도 적게 사용하고 훨씬 빠르게 정답을 찾아낼 수 있었다. 코드 모든 칸에 BFS 실행 from collections import deque import sys N, M = map(int, sys.stdin.readline().split(...