이번 문제는 BFS를 이용하여 갈 수 있는 공간 중 조건에 부합하는 위치로 이동하는 과정을 더이상 움직일 수 없을 때까지 반복하는 방식으로 접근하였다. 답을 찾아보지 않고 풀이하여 시간이 오래 걸렸지만 그만큼 얻은게 많은 문제이다.

• n을 입력받는다.
• 공간을 grid에 입력받는다.
• 상어의 위치를 나타내는 변수 cur_y, cur_x를 0으로 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 grid[i][j]가 9일 경우,
  ---> cur_y, cur_x를 i, j로 갱신한다.
  ---> grid[i][j]를 0으로 갱신한다.
  ---> 반복문을 종료한다.
• 아기 상어의 크기에 해당하는 변수 baby를 2로 선언한다.
• 방향에 해당하는 리스트 dy, dx를 상, 좌, 우, 하 순서로 저장한다.
• bfs함수를 cur_y, cur_x를 인자로 갖도록 선언한다.
  -> q를 deque로 선언한다.
  -> q에 (0, cur_y, cur_x, 0)을 넣는다.
  -> 방문 처리 리스트 visited를 n*n의 크기로 선언하고, False를 채운다.
  -> visited[cur_y][cur_x]를 True로 갱신한다.
  -> 잡아 먹을 수 있는 물고기의 위치를 저장할 리스트 results를 선언한다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> d, y, x, flg를 q에서 추출한다.
  --> 최소 거리를 저장할 변수 md를 sys.maxsize로 선언한다.
  --> 만약 flg가 1이고, d가 md보다 작거나 같을 경우,
  ---> md를 d로 갱신한다.
  ---> results에 (d, y, x)를 넣는다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny, nx를 y+dy[i], x+dx[i]로 갱신한다.
  ---> 만약 ny가 0 이상, n 미만이고, nx가 0 이상, n 미만이고, visited[ny][nx]가 False일 경우,
  ----> 만약 grid[ny][nx]가 0보다 크고, baby보다 작을 경우,
  -----> visited[ny][nx]를 True로 갱신한다.
  -----> q에 (d+1, ny, nx, 1)을 넣는다.
  ----> 만약 grid[ny][nx]가 baby와 같거나 grid[ny][nx]가 0일 경우,
  -----> visited[ny][nx]를 True로 갱신한다.
  -----> q에 (d+1, ny, nx, 0)을 넣는다.
  -> 만약 results가 비어있을 경우,
  --> [-1, -1, -1]을 출력한다.
  -> results를 오름차순 정렬한다.
  -> results[0]을 반환한다.
• 결과를 저장할 변수 answer를 0으로 선언한다.
• 카운팅 변수 cnt를 0으로 선언한다.
• while문을 돌린다.
  -> time, cur_y, cur_x를 bfs(cur_y, cur_x)로 저장한다.
  -> 만약 [time, cur_y, cur_x]가 [-1, -1, -1]과 같을 경우,
  --> answer를 출력한다.
  --> while문을 종료한다.
  -> answer에 time을 더한다.
  -> grid[cur_y][cur_x]를 0으로 선언한다.
  -> cnt를 1 증가시킨다.
  -> 만약 cnt가 baby와 같을 경우,
  --> baby를 1 증가시킨다.
  --> cnt를 0으로 갱신한다.

Code

import sys
from collections import deque
n=int(input())
grid=[list(map(int, input().split())) for _ in range(n)]
cur_y, cur_x=0, 0
for i in range(n):
    for j in range(n):
        if grid[i][j]==9:
            cur_y, cur_x=i, j
            grid[i][j]=0
            break
baby=2
dy, dx=[-1, 0, 0, 1], [0, -1, 1, 0]
def bfs(cur_y, cur_x):
    q=deque()
    q.append((0, cur_y, cur_x, 0))
    visited=[[False]*n for _ in range(n)]
    visited[cur_y][cur_x]=True
    results=[]
    while q:
        d, y, x, flg=q.popleft()
        md=sys.maxsize
        if flg==1 and md>=d:
            md=d
            results.append((d, y, x))
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
                if 0<grid[ny][nx]<baby:
                    visited[ny][nx]=True
                    q.append((d+1, ny, nx, 1))
                elif grid[ny][nx]==baby or grid[ny][nx]==0:
                    visited[ny][nx]=True
                    q.append((d+1, ny, nx, 0))
    if not results:
        return [-1, -1, -1]
    results.sort(key=lambda x: (x[0], x[1], x[2]))
    return results[0]
answer=0
cnt=0
while True:
    time, cur_y, cur_x=bfs(cur_y, cur_x)
    if [time, cur_y, cur_x]==[-1, -1, -1]:
        print(answer)
        break
    answer+=time
    grid[cur_y][cur_x]=0
    cnt+=1
    if cnt==baby:
        baby+=1
        cnt=0