N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
아기 상어는 공간에 한 마리 있다.
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
from collections import deque
N =int(input())
grid = [list(map(int,input().split())) for _ in range(N)]
#방향
dr = [-1,0,1,0]
dc = [0,-1,0,1]
#물고기수
fish = 0
#상어 최초 크기
shark = 2
#먹은 물고기 수
eat = 0
#아기상어 위치가 시작 위치
for r in range(N):
for c in range(N) :
#상어 위치
if grid[r][c] == 9 :
sr,sc = r,c
grid[r][c] = 0
#물고기 수
elif 0<grid[r][c] <=6 :
fish += 1
#아기상어 시작 위치와 크기 배열에 넣기
def bfs(sr,sc) :
q = deque([(sr,sc,0)])
#물고기까지 거리를 담을 리스트
dist_lst = []
#방문배열
visited =[[0]*N for _ in range(N)]
visited[sr][sc] = 1
min_dist = 1e9
#큐가 빌때까지
while q :
#꺼내고
r,c,dist = q.popleft()
#4방향 탐색
for d in range(4) :
nr = r + dr[d]
nc = c + dc[d]
#거리 안에 있으면서 방문하지 않았을 때 #나보다 작거나 같으면 방문한다.
if 0<=nr<N and 0<=nc <N and not visited[nr][nc] and grid[nr][nc] <= shark :
visited[nr][nc] = 1
#상어보다 작으면 해당 상어까지 거리를 최소거리로 갱신하고 후보에 넣는다.
if 0< grid[nr][nc] < shark :
min_dist = dist
dist_lst.append((nr,nc,dist+1))
#한 칸 더 탐색할 곳이 최소거리보다 작다면 큐에 추가해서 탐색한다.
if dist + 1 <=min_dist :
q.append((nr,nc,dist+1 ))
if dist_lst :
dist_lst.sort(key=lambda x:(x[2],x[0],x[1]))
return dist_lst[0]
#소요시간
time = 0
#남은 물고기가 있을 때
while fish :
#현 위치에서 가장 가까우면서 먹을 수 있는 물고기를 찾는다.
result = bfs(sr,sc)
#먹을 물고기가 없으면 멈춘다.
if not result :
break
#물고기를 찾으면 그 위치가 내 자리
sr,sc = result[0],result[1]
#걸린 시간에 물고기한테 가는데 걸린 거리를 더한다.
time += result[2]
#먹은 물고기
eat += 1
#남은 물고기
fish -=1
#상어 크기와 먹은 물고기가 같으면
if shark == eat :
#상어 크기 더하고
shark += 1
#물고기 수 추가
eat = 0
#물고기 먹었으니까 자리 없애기
grid[sr][sc] = 0
print(time)