16236 - 아기상어*

# 가장 가까운 거리에 있는 물고기부터 순차적으로 탐색하면서 상어와 물고기와의 거리 찾음(먹을 수 있는 물고기만)
from collections import deque
def bfs(x, y):
    q = deque([[x, y]])
    visited = [[False]*N for _ in range(N)]
    visited[x][y] = True
    distance = [[0]*N for _ in range(N)]
    locAndDistance = []
    while q:
        sx, sy = q.popleft()
        for i in range(4):
            nx = sx+dx[i]
            ny = sy+dy[i]
            if 0<=nx<N and 0<=ny<N and visited[nx][ny] == False:
                # 아기상어보다 몸이 크거나, 아기상어가 있는 곳은 지나가지 못함
                # 빈공간 또는 아기상어보다 작거나 같은 물고기가 있는 곳은 지나갈 수 있음
                if graph[nx][ny]<=sharkSize:
                    visited[nx][ny] = True
                    q.append([nx, ny])
                    # 상/하/좌/우 중 하나로 이동하므로 거리는 무조건 1 증가
                    distance[nx][ny] = distance[sx][sy] + 1
                    # 물고기가 상어보다 작은 경우라면 먹을 수 있으므로, locAndDistance에 저장
                    if graph[nx][ny]<sharkSize and graph[nx][ny] != 0:
                        locAndDistance.append([nx, ny, distance[nx][ny]])

    # 거리가 짧은 순 -> 위쪽에서 순(가장 위 물고기) -> 왼쪽 순(가장 왼쪽 물고기)
    locAndDistance.sort(key=lambda x: (x[2], x[0], x[1]))

    return locAndDistance

# 아기 상어의 크기는 2
# 큰 물고기가 있는 칸은 지나갈 수 없음
# 같은 물고기는 지나만 갈 수 있음
# 작은 물고기는 먹을 수 있음 -> 자신의 크기와 같은 수의 물고기를 먹을때마다 크기가 1씩 증가

# 먹을 수 있는 물고기가 없으면 엄마 상어에 도움 요청
# 먹을 수 있는 물고기가 1마리면 그 물고기 먹으러 이동
# 먹을 수 있는 물고기가 2마리 이상이라면 가장 가까운 물고기를 먹으러 감
# 위쪽 -> 왼쪽 물고기가 우선순위가 높음

# 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있음?
if __name__ == '__main__':
    N = int(input())
    graph = []
    for r in range(N):
        temp = list(map(int, input().split()))
        graph.append(temp)
        if 9 in temp:
            sharkLoc = [r, temp.index(9)]

    sharkSize = 2; time = 0; cnt = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    eatChk = [[False] * N for _ in range(N)]

    while True:
        x = sharkLoc[0]
        y = sharkLoc[1]
        locAndDistance = bfs(x, y)
        if len(locAndDistance) == 0:
            break
        fishxyd = locAndDistance.pop(0)
        fx = fishxyd[0]
        fy = fishxyd[1]
        d = fishxyd[2]
        time += d; cnt += 1
        sharkLoc = [fx, fy]
        graph[x][y] = 0; graph[fx][fy] = 0
        x = fx; y = fy

        if cnt == sharkSize:
            sharkSize += 1
            cnt = 0

    print(time)