[백준, 파이썬, 17086번] 아기 상어 2

 

풀이

 

• 분명 정말 전까지 많이 풀었던 그래프 탐색 문제인데
• 로직은 이해가 가는데 기존 풀었던 로직과의 차이점으로 조금 걸렸다.
• 이유는 기존 로직은 해당 스팟에서부터 q에 요소가 없을 때까지 돌리는 문제인데
• 해당 문제는 모든 스팟 즉, 각 상어 위치로부터 점차 확장해 나가며 최대 허용거리를 측정하는 것이기에
• 모든 위치를 q에 넣은 다음 bfs로 풀어야 해결이 되는 문제였기에 오래걸렸다...

 

import sys

from collections import deque

input = sys.stdin.readline

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

mtx = [list(map(int,input().rstrip('\n').split())) for _ in range(n)]

q = deque([])

result = 0

for i in range(n):

    for j in range(m):

        if mtx[i][j]:

            q.append([i,j])

while q:

    y,x = q.popleft()

    for dy,dx in [[y-1,x],[y-1,x+1],[y,x+1],[y+1,x+1],[y+1,x],[y+1,x-1],[y,x-1],[y-1,x-1]]:

        if 0<=dy<n and 0<=dx<m and not mtx[dy][dx]:

            mtx[dy][dx] = mtx[y][x]+1

            result = max(result, mtx[y][x]+1)

            q.append([dy,dx])

print(result-1)