백준 17086번

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

17086번: 아기 상어 2

from collections import deque

n, m = map(int,input().split())

g = [list(map(int,input().split())) for _ in range(n)]

#8방향
way = [[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1]]

ans = 0
#큐 생성
q = deque()

def bfs():
  
  while q:
    
    x,y= q.popleft()
    # 8방향으로 탐색
    for i in range(len(way)):
      nx = x + way[i][0]
      ny = y + way[i][1]

      # 이동할 수 있는 경우
      if n>nx>=0 and m>ny>=0:
        # 방문한 적 없는 경우 
        if g[nx][ny]==0:
          #큐에 추가
          q.append((nx,ny))
          #기존거리에서 1더해주기
          g[nx][ny] = g[x][y]+1

          
for i in range(n):
  for j in range(m):
    # 상어가 있는 곳을 큐에 추가
    if g[i][j]==1:
        q.append([i,j])

bfs()

#그래프에서 가장 큰 값 - 1
print(max(map(max,g))-1)

 

 

1. 상어가 위치한 곳을 큐에 추가
2. bfs를 이용하여 상어가 위치한 곳부터 8방향 으로 탐색
3. 이동할 수 있고 방문 한 적이 없는 위치면 기존 거리에서 1을 더해 큐에 추가
4. 그래프에서 가장 큰 값에서 초기 값 1을 빼준 것이 정답