문제
input
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
0: 빈 칸
1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
9: 아기 상어의 위치
아기 상어는 공간에 한 마리 있다.
output
첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다. 먹을 수 있는거 다먹은 시간
TODO
입력값 처리 -> 물고기 크기, 상어의 위치 저장
물고기 크기 순 정렬
현재 상어 위치(x,y),시간(t) = pos : deque
물고기 크기 순 = fish : deque
먹은 물고기 수 = cnt = 0
상어 크기 = size = 2
while pos, fish, size > fish[0]:
if 현재시간에 먹을 물고기가 없다면
상어가 다음 먹을 물고기 찾기 ->bfs
elif 같은 시간(T)내에 먹을 수 있는 물고기가 한 마리 이상 있다면 :
R = min(r1,r2,...,rn)
같은 r이 여러개라면
C = min(c1,c2,...,cn)
pos = [(R,C,T)]
fish.popleft() #먹은 물고기를 삭제하는거 아님
cnt +=2
if cnt == size :
size+=1
cnt=0 CODE
from collections import deque
def move(x,y,fish,space,n):
t=0
position = deque([(x,y,t)])
check = [[True for _ in range(n)] for _ in range(n)]
check[x][y] = False
dx = [-1,0,0,1]
dy = [0,-1,1,0]
size = 2
cnt = 0
time = deque()
answer = 0
while fish and size > fish[0] and position :
if t == position[0][2] or not time :
x,y,t = position.popleft()
for px,py in zip(dx,dy):
nx,ny = x+px, y+py
if 0<=nx<n and 0<=ny<n and check[nx][ny] and space[nx][ny]<=size:
check[nx][ny] = False
if 0<space[nx][ny]<size :
time.append((nx,ny,t+1))
position.append((nx,ny,t+1))
else :
position.append((nx,ny,t+1))
else :
fish.popleft()
nx,ny = float('inf'),float('inf')
for ti in time :
if ti[0] < nx :
nx,ny = ti[0], ti[1]
answer = ti[2]
elif ti[0] == nx and ti[1] < ny :
nx,ny = ti[0], ti[1]
answer = ti[2]
space[nx][ny] = 0
cnt += 1
if cnt == size :
size += 1
cnt = 0
position = deque([(nx,ny,answer)])
time = deque()
for i in range(n):
for j in range(n):
check[i][j] = True
check[nx][ny] = False
return answer
if __name__ =="__main__":
n = int(input())
space = [list(map(int,input().split())) for _ in range(n)]
x,y= 0,0
fish = []
for i in range(n):
for j in range(n):
if space[i][j] != 0 :
if space[i][j] == 9 :
x,y= i,j
space[i][j] = 0
else :
fish.append(space[i][j])
fish = deque(sorted(fish))
print(move(x,y,fish,space,n))회고
[(-1,0),(0,-1),(0,1),(1,0)] 순으로 우선순위를 정하면 안된다.
밑에 반례보면 알겠지만 큰 코 다친다.
코드 한 번 다 갈았다.
TDD하자.
반례
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6
->60
문제에 제공된 예시인데 먹는걸 보면 10초?쯤에 (0,2)에 있는 3을 먹는다.
다음으로 먹는 물고기는 2초후에 먹을 수 있는 (0,4)와 (1,1)의 물고기가 있다. 문제의 조건에 따르면 (0,4)를 먹어야하지만 우선순위를 상 좌 우 하 로 하면 (1,1)을 먹는다.
바보같은놈 ㅂㄷㅂㄷ
6
1 0 0 0 0 0
6 6 6 6 6 0
1 0 6 0 9 0
2 0 6 0 6 6
6 0 0 0 6 6
6 6 6 6 6 6
->25
[(-1,0),(0,-1),(0,1),(1,0)] 순으로 우선순위를 정하면 안된다.
-> 맨 처음 상어는 같은 거리에 있는 두개의 1중 아래 있는 1을 먹게 된다.
3
0 1 1
5 5 5
0 9 0
-> 0
생선 못먹는다. ㅂㄷㅂㄷ
