BOJ 17086 - 아기 상어2

문제

백준 온라인 저지 - 17086번

풀이 과정

아기 상어에 도달하는 가장 가까운 거리를 안전 거리 라고 표현합니다.
이 안전 거리 중에서 가장 큰 값을 찾아야하기 때문에 상어가 없는 각 칸마다 BFS 를 수행해서 안전 거리 를 계산하면 됩니다.

코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


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


def bfs(x, y):
    visit = [[0]*M for _ in range(N)]
    q = deque()

    visit[x][y] = 1
    q.append([x, y, 0])

    while q:
        x, y, cost = q.popleft()
        if board[x][y]:
            return cost

        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny]:
                    visit[nx][ny] = 1
                    q.append([nx, ny, cost + 1])


def solution():
    answer = 0

    for x in range(N):
        for y in range(M):
            if not board[x][y]:
                answer = max(answer, bfs(x, y))

    return answer


print(solution())