백준 17086번 아기 상어 2 (Python 3)

Baekjoon online judge 17086번 파이썬

 

링크

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

17086번: 아기 상어 2

모든 0인 점에 대해서 bfs를 수행, 1을 만나면 now_max에 값을 반영하고 bfs종료

데이터가 커지면 복잡도가 너무 커져서 이 방법으로는 못풀것같다.

더 효율적인 풀이가 있을것 같다.

+추가

bfs가 필요 없었다.

1의 위치를 미리 저장해놓고, 각 0에 대해서 1의 위치들과의 거리를 구한다. 그 중에 최소값을 now_max에 반영하면 bfs없이도 풀수있다. 이 쪽이 1이 적을 떄는 훨씬 빠르다.

소스코드

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

def bfs(x,y):
  global now_max
  queue=deque()
  queue.append([x,y,0])
  visited=[[False for _ in range(m)] for _ in range(n)]
  visited[y][x]=True

  while queue:
    qx,qy,cnt=queue.popleft()
    if map_data[qy][qx]==1:
      now_max=max(now_max,cnt)
      return
    for indx,indy in index:
      nx=qx+indx
      ny=qy+indy
      if 0<=nx<m and 0<=ny<n and not visited[ny][nx]:
        visited[ny][nx]=True
        queue.append([nx,ny,cnt+1])




n,m=map(int,input().split())
index=[[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]
map_data=[list(map(int,input().split())) for _ in range(n)]
now_max=-1


for i in range(n):
  for j in range(m):
    if map_data[i][j]==0:
      bfs(j,i)
print(now_max)