문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
• 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

풀이

BFS를 이용하여 최단거리를 찾고 반복하는 문제였다.
이동가능한 위치와 잡아 먹을 수 있는 위치를 구별해주어야 한다.
이동 중에 현재 최단거리보다 멀어지는 경우 탐색을 중단해 주어야 시간초과를 피할 수 있었다.
추가적으로 같은 거리에 대한 우선순위가 주어져서 풀이에 시간이 걸렸다.

풀이 순서
1. 배열을 돌면서 아기 상어를 찾으면 BFS시작
2. 처음위치 방문 처리 후 좌표 큐에 삽입
3. 사방탐색하여 이동가능한 위치라면 거리 표시하면서 이동
4. 이동 중에 최단거리보다 멀어질 경우 중단, 아니면 큐에 좌표 삽입
5. 이동한 위치에 잡아 먹을 수 있는 먹이가 있으면 리스트에 저장
6. 큐의 원소가 없어지면 먹이 리스트를 우선순위대로 정렬 후 해당 위치로 이동
7. 사이즈만큼 먹은 경우 성장
8. 먹이 리스트와 큐 초기화 후 재귀 호출 (2번부터 다시 반복)

import sys

input = sys.stdin.readline
from collections import deque


def hunt(r, c, size):
    global cnt
    global catch
    q.append((r, c))
    # 시작점 방문처리
    v = [[0] * N for _ in range(N)]
    v[r][c] = 1
    while q:
        si, sj = q.popleft()

        for k in range(4):
            ni = si + dx[k]
            nj = sj + dy[k]
            # 범위 안에 있고 사이즈 이하면 이동
            if 0 <= ni < N and 0 <= nj < N and arr[ni][nj] <= size:
                if v[ni][nj] == 0:
                    # 이동거리 표시
                    v[ni][nj] = v[si][sj] + 1
                    if food:
                        # 이동거리가 먹이위치보다 멀어지면 건너뜀
                        if v[ni][nj] > food[-1][-1]:
                            continue
                        else:
                            q.append((ni, nj))
                    else:
                        q.append((ni, nj))

                    # 이동 위치가 0이 아니고 사이즈보다 작으면
                    if arr[ni][nj] != 0 and arr[ni][nj] < size:
                        if food:
                            # 이동거리가 먹이 위치 이하면 리스트 추가
                            if v[ni][nj] <= food[-1][-1]:
                                food.append((ni, nj, v[ni][nj]))

                        else:
                            food.append((ni, nj, v[ni][nj]))
    if food:
        ni, nj = catch_near()
        catch += 1
        # 이동시간 추가
        cnt += v[ni][nj] - 1
        # 잡아먹어서 물고기 사라짐
        arr[ni][nj] = 0
        # 잡아먹은 수가 사이즈만큼이면 성장
        if catch == size:
            size += 1
            catch = 0
        # 이동위치에서 새로 시작
        q.clear()
        food.clear()
        hunt(ni, nj, size)


# 제일 위, 제일 왼쪽이 우선으로 정렬
def catch_near():
    food.sort(key=lambda x: (x[0], x[1]))
    return food[0][0], food[0][1]


N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
q = deque()
food = []
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
cnt = 0
catch = 0
for i in range(N):
    for j in range(N):
        if arr[i][j] == 9:
            # 시작점 0
            arr[i][j] = 0
            hunt(i, j, 2)
print(cnt)