[백준/Python] 17086. 아기상어 2

 

• bfs를 활용하여 풀었다.

import sys
from collections import deque
input = sys.stdin.readline                  # 입력 시간을 줄이기 위한 코드

N, M = map(int, input().split())
arr = []
q = deque()
Max = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    arr.append(tmp)

for j in range(N):
    for i in range(M):
        if arr[j][i] == 1:                  # 입력을 전부 다 받고 완전탐색을 통해 1이 있다면 그 위치를 q에 추가시켜줌
            q.append([j,i])

def bfs():
    global Max
    directy = [-1,-1,-1,0,0,1,1,1]
    directx = [-1,0,1,-1,1,-1,0,1]

    while q:
        y,x = q.popleft()

        for k in range(8):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0:
                continue                    # y축과 x축의 인덱스를 벗어난다면 continue
            elif arr[dy][dx] == 0:
                arr[dy][dx] = arr[y][x] + 1 # arr[dy][dx] == 0 이라면 아직 방문하지 않았다는 뜻 이므로 그 위치에 이전 값에 +1을 해줌
                if arr[dy][dx] >= Max:      # Max값을 비교하여 만약 Max값보다 크다면 갱신
                    Max = arr[dy][dx]
                q.append([dy,dx])           # q에 현재 위치를 추가해줌

bfs()

print(Max-1)                                # 출력할 땐 1부터 시작했으므로 1을 빼줘야함