✅문제 요약

1. nxn 배열
2. 빈칸 0 상어 9 물고기 M마리
3. 처음 상어의 크기2, 물고기는 각 크기를 가짐
4. 상어는 자신보다 작은 크기의 물고기를 먹음. 큰 물고기의 위치는 못 지나감. 같은 크기는 지나가기만 가능
5. 먹을 수 있는 물고기가 없다면 종료
6. 먹을 수 있는 물고기가 1마리면 바로 먹으러 감
7. 많다면 가장 가까운 물고기를 먹는다
8. 거리가 같은 물고기가 많다면 가장 윗칸, 그래도 많다면 가장 왼쪽 물고기를 먹는다
9. 자신의 크기와 같은 수의 물고기를 먹을 때 크기가 1 증가한다.
10. 1칸 이동시 1초가 지난다면 상어는 몇초동안 물고기를 먹는지 출력

✅문제 풀이

문제에서 내세운 조건이 많다 == 구현/시뮬레이션 문제다
이동하며 탐색한다 == 90% 확률로 BFS문제다
문제에서 가장 까다롭다고 꼽을 수 있는 조건은 바로 8, 9번이다
=> 탐색을 윗쪽, 왼쪽 부터 탐색하며 먹이 배열을 담아서 후에 조건문으로 해결했다

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
direct = [(-1, 0), (0, -1), (1, 0), (0, 1)]


nr, nc = 0, 0
for a in range(N):
    for b in range(N):
        if arr[a][b] == 9:
            arr[a][b] = 0
            nr, nc = a, b                       # 상어위치 및 0 처리
            break

me, eat, ans = 2, 0, 0                          # 상어크기, 먹은 고기 수, 출력할 답
while True:
    Q = deque([(nr, nc)])
    feed = []                                   # 먹이 배열
    min_d = N*N                                 # 최단거리 초기화
    visit = [[0]*N for _ in range(N)]
    visit[nr][nc] = 1
    while Q:
        x, y = Q.popleft()


        if 0 != arr[x][y] < me:
            min_d = min(min_d, visit[x][y])
            feed.append((x, y))

        for d in direct:
            dx, dy = x+d[0], y+d[1]
            if 0 <= dx < N and 0 <= dy < N and not visit[dx][dy] and arr[dx][dy] <= me:
                 visit[dx][dy] = visit[x][y]+1
                 Q.append((dx, dy))

    if feed:                                 # 먹을 수 있는 고기가 있을 때 반복
    	# 가장 가까운 > 가장 위 > 가장 좌측 물고기 탐색
        r, c = N, N
        for i, j in feed:
            if visit[i][j] == min_d:
                if i < r:
                    r, c = i, j
                elif r == i and c > j:
                    c = j
        arr[r][c] = 0
        ans += visit[r][c]-1
        nr, nc = r, c
        eat += 1
        if eat == me:
            me += 1
            eat = 0

    else:                                       # 먹을 수 없다면 ans 출력
        print(ans)
        exit()