BFS, 구현 - 16236번: 아기 상어

import sys
from collections import deque


input = sys.stdin.readline

n = int(input())

maps = []
s_size = 2  # 초기 상어 크기(2)
s_pos_x = -1  # 상어 x좌표(행)
s_pos_y = -1  # 상어 y좌표(열)
sec = 0  # 누적 시간

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

for i in range(n):
    line = list(map(int, input().rstrip().split()))
    for j in range(len(line)):

        if line[j] == 9:  # 상어 초기 좌표 초기화하기
            s_pos_x, s_pos_y = i, j
            line[j] = 0  # 맵에는 빈공간으로 표시

    maps.append(line)


def check_possible_fish():

    visited = [[False] * n for _ in range(n)]

    queue = deque()
    queue.append((s_pos_x, s_pos_y, 0))

    visited[s_pos_x][s_pos_y] = True

    # 현재 상어의 위치 및 크기일 때 접근해서 먹을 수 있는 후보 물고기 리스트
    eat_candidates = []

    while queue:
        x, y, dist = queue.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (
                0 <= nx < n
                and 0 <= ny < n
                and maps[nx][ny] <= s_size
                and not visited[nx][ny]
            ):
                fish_size = maps[nx][ny]

                # 현재 자리에 물고기가 있는데(0 < maps[nx][ny]) 그 크기가 상어보다 작다면
                if 0 < fish_size < s_size:
                    # 후보 물고기 리스트에 추가, 그 뒤는 더 볼 필요 없음 (거리 상 가까운 물고기 먼저 먹기 때문에)
                    eat_candidates.append((nx, ny, dist + 1))
                else:  # 빈 공간이거나 물고기 크기가 상어랑 동일하다면 지나갈 수 있음
                    # 큐에 추가
                    queue.append((nx, ny, dist + 1))
                # 방문 처리
                visited[nx][ny] = True

    if len(eat_candidates) > 1:
        # 거리, 행, 열 순으로 정렬
        eat_candidates.sort(key=lambda x: (x[2], x[0], x[1]))

    return eat_candidates


eat_cnt = 0

while True:

    eat_candidates = check_possible_fish()

    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청
    if len(eat_candidates) == 0:
        break
    else:
        # 먹은 물고기 수 업데이트
        eat_cnt += 1
        # 상어 해당 물고기 자리로 이동
        s_pos_x, s_pos_y = eat_candidates[0][0], eat_candidates[0][1]
        # 먹어서 빈 공간으로 바꾸기
        maps[eat_candidates[0][0]][eat_candidates[0][1]] = 0
        # 이동 거리만큼 시간 누적
        sec += eat_candidates[0][2]

    # 상어 사이즈 키우기 (자신의 크기만큼의 마릿수를 먹으면 +1 커짐)
    if eat_cnt == s_size:
        s_size += 1
        eat_cnt = 0


print(sec)