백준 16236번: 아기상어

from collections import deque


n=int(input())
graph=[]
for i in range(n):
    graph.append(list(map(int,input().split())))

for i in range(n):
    for j in range(n):
        if graph[i][j]==9: #아기상어의 위치
            shark_x,shark_y=i,j #아기상어의 위치 저장
            graph[i][j]=0 #빈칸으로 변경

level=2


dx=[1,-1,0,0]
dy=[0,0,1,-1]
def bfs(x,y,level):
    visited=[[0]*n for i in range(n)]
    dist=[[0]*n for i in range(n)]
    queue=deque()
    queue.append((x,y))
    
    visited[x][y]=1 #방문표시
    fish=[]
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            if graph[nx][ny]<=level and visited[nx][ny]==0: #상어가 이동가능한 경우
                queue.append((nx,ny))
                visited[nx][ny]=1
                dist[nx][ny]=dist[x][y]+1
                if graph[nx][ny]<level and graph[nx][ny]>0: #물고기일 때
                    fish.append((nx,ny,dist[nx][ny]))
    visited=[[0]*n for i in range(n)]
    return sorted(fish,key=lambda x:(-x[2],-x[0],-x[1])) #거리, 윗쪽, 왼쪽 순 정렬


count=0
result=0
exp=0
while True:
    shark=bfs(shark_x,shark_y,level) #bfs함수로 먹을 수 있는 물고기의 위치,거리를 받음
    if len(shark)==0: #먹을 물고기가 없는 경우 중단
        break

    nx,ny,dist=shark.pop() #먹을 물고기의 위치,거리를 nx,ny,dist에 담음

    result+=dist #총 걸린 시간에 거리만큼 더함
    graph[shark_x][shark_y],graph[nx][ny]=0,0 #먹은 물고기 위치를 0으로 변경
    shark_x,shark_y=nx,ny #현재위치를 물고기를 먹은 위치로 변경

    exp+=1
    if exp==level:
        level+=1
        exp=0

print(result)

...