백준[ 17086 | Python ] 아기 상어2

문제

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

풀이

각 칸으로부터 상어의 위치까지의 거리 중 가장 큰 값을 찾아내는 문제이다.
목표 값이 아닌 값부터 시작했던 이 전에 풀었던 BFS문제와는 다르게
해당 문제는 목표 값으로부터 시작하는게 편리하다.

상어의 위치를 먼저 찾아 deque에 넣어준 후 해당 상어들의 위치로부터 각 비어있는 칸까지의 거리를
그래프에 넣어주고 만들어진 그래프 안에서 최대값을 추출한다.

이 때 주의할 점은 상어의 유무를 표현하는 1을 거리로 사용했기 때문에 그 값을 마지막 결과에서 빼주어야한다.

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

N,M = map(int,(input().split()))

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

dx = [-1,-1,-1,0,1,1,1,0]
dy = [-1,0,1,1,1,0,-1,-1]

q = deque()
    
def bfs():
    while q:
        nx, ny = q.popleft()
        for i in range(8):
            qx, qy = nx + dx[i], ny + dy[i]
            if 0 <= qx < N and 0 <= qy < M and not board[qx][qy]:
                q.append((qx,qy))
                board[qx][qy] = board[nx][ny] + 1
             
for i in range(N):
    for j in range(M):
        if board[i][j]:
            q.append((i,j))
bfs()
print(max(map(max,board))-1)

생각 & 정리

bfs문제를 다시 접한지 오래되지 않았는데, 때에 따라서 방문 확인을 하는 visited 배열을
그래프에 직접 사용할 수 있다는 것을 잊었다.
또한 문제에서 주어진대로 순서에 따라 진행하는 것보다 반대로 시작하는 것 또한 용이할 수 있다는 것을
유념해두어야 하는 문제였다.