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로 이루어져 있고, 아래와 같은 의미를 가진다.
아기 상어는 공간에 한 마리 있다.
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.
check
에 담긴 좌표들이 다시 bfs를 돌려야 하는 q가 된다.chekc
가 담은 것은 지나갈 수 있는 0 또는 무게만 같은 좌표들을 담아 주었다. from collections import deque
def bfs(sti, stj, weight, cnt):
global res
q = deque([])
i, j = sti, stj
q.append((i, j))
visited = [[0] * n for _ in range(n)]
visited[i][j] = 1
distance = 0
while q:
distance += 1
check = deque([])
eat = []
for x, y in q:
for dx, dy in [(-1,0), (0,-1), (1, 0), (0, 1)]:
nx, ny = x + dx, y + dy
# 먹을 수 있는 애들 담기
if 0 <= nx < n and 0 <= ny < n and 0 < arr[nx][ny] < weight and not visited[nx][ny]:
eat.append((nx, ny))
# 지나갈 수 있는 애들 담기
elif 0 <= nx < n and 0 <= ny < n and (arr[nx][ny] == 0 or arr[nx][ny] == weight) and not visited[nx][ny]:
check.append((nx,ny))
visited[nx][ny] = 1
if eat:
eat.sort()
i, j = eat[0]
cnt += 1
arr[i][j] = arr[sti][stj] = 0
res += distance
if cnt == weight:
weight += 1
cnt = 0
return bfs(i, j, weight, cnt)
q = check
return
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
res = 0 # 시간
for i in range(n):
for j in range(n):
if arr[i][j] == 9:
sti, stj = i, j
break
bfs(sti, stj, 2, 0)
print(res)