링크 : https://www.acmicpc.net/problem/16236
from collections import deque
from sys import stdin
input = stdin.readline
n = int(input())
graph = [ list(map(int, input().split())) for _ in range(n) ]
x, y, size = 0, 0, 2
for i in range(n): # 아기 상어의 위치를 찾고 아기상어 위치 좌표와 사이즈(2) 초기화
for j in range(n):
if graph[i][j] == 9:
x, y = i, j
break
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def biteFish(x, y, shark_size):
distance = [ [0] * n for _ in range(n) ]
visited = [ [False] * n for _ in range(n) ]
q = deque()
q.append((x, y))
visited[x][y] = True
temp = [] # 상어가 먹잇감을 마주 쳤을때 해당 좌표와 움직인 거리 : (먹잇값의 좌표, 움직인 거리)
while q:
px, py = q.popleft()
for k in range(4):
mx = px + dx[k]
my = py + dy[k]
if 0 <= mx < n and 0 <= my < n and not visited[mx][my]:
if graph[mx][my] <= shark_size:
q.append((mx, my))
visited[mx][my] = True
distance[mx][my] = distance[px][py] + 1
if graph[mx][my] < shark_size and graph[mx][my] != 0: # 상어가 실제 먹잇감을 발견했을 때 해당 좌표와 이때까지 움직인 거리 기록
temp.append((mx, my, distance[mx][my]))
# 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면 가장 왼쪽에 물고기를 먹도로 좌표를 정렬한다.
# 거리순 x[2] 으로 정렬 후 x[0], x[1] 순으로 정렬한다면 가장 위, 가장 왼쪽의 물고기 좌표가 먼저오도록 설정된다.
return sorted(temp, key=lambda x : (x[2], x[0], x[1]))
cnt = 0
result = 0
while 1:
shark = biteFish(x, y, size)
# 더이상 먹을 수 있는 물고기가 없다면 엄마상어에게 도움 요청
if len(shark) == 0:
break
# 가장 가까이 있는 물고기중 가장 위쪽, 가장 왼쪽에 있는 물고기를 꺼낸다.
mx, my, dist = shark.pop(0)
# 움직이는 거리 = 걸린 시간
result += dist
# 상어의 처음위치랑, 상어가 물고기를 잡아먹고 난 뒤의 좌표는 0으로 초기화 한다.
graph[x][y], graph[mx][my] = 0, 0
# 상어의 처음 위치를 물고기를 잡아먹고 난 뒤의 좌표로 옮겨준다.
x, y = mx, my
# 물고기를 잡아먹은 횟수
cnt += 1
# 물고기를 잡아먹은 횟수와 상어의 사이즈가 같다면 사이즈를 높여주고 잡아먹은 횟수는 다시 초기화
if cnt == size:
size += 1
cnt = 0
print(result)