https://www.acmicpc.net/problem/16236
16236번: 아기 상어N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가www.acmicpc.net
가장 어려웠던 조건이
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다
였다.
처음에는 방향 순서만 잘 하면 될 줄 알았지만,
디버깅해보면 방향만으로는 부족하다.
한참 헤메다가 질문계시판에서 정렬 힌트를 얻고 풀었다.
결국 ‘해당 거리에서 먹을수 있는 모든 물고기들’ 을 모아놓고,
이를 정렬하여 ‘가장 위,왼쪽의 물고기’ 를 먹는 식으로 구현하면 된다.
나는 물고기의 시간이 바뀔때마다 heap안에 물고기가 있는지 확인하고, pop하는 식으로 구현했다.
이 아이디어만 알면 쉽게 풀리는데, 이 아이디어를 어떻게 생각하는지 모르겠다.
import sysinput =sys.stdin.readlinefrom collections import dequeimport heapq
move=[[-1,0],[0,-1],[0,1],[1,0]] #움직임n=int(input())Flag=Falsearr=[]
for i in range(n): tmp=[*map(int,input().split())] arr.append(tmp)
for j in range(n): if not Flag: if tmp[j]==9:
shark=[i,j] #입력받기 Flag=0
arr[shark[0]][shark[1]]=0 #상어표시된거 초기화 !중요size=2 #크기eat=0 #먹은횟수answer=0
###############################################################
def bfs(shark:list): visited=[[0 for _ in range(n)] for _ in range(n)] #방문처리용
visited[shark[0]][shark[1]]=1 #현재있는곳방문처리
que=deque([[0]+shark]) #shark = x,y,t heap=[] # 물고기판별용 tt=0
while que: t,cx,cy=que.popleft() if t!=tt: #한사이클이 돌았으면
tt+=1 if heap: #만일 물고기가있다면
return heapq.heappop(heap)
for dx,dy in move: nx,ny=cx+dx,cy+dy
if 0<=nx<n and 0<=ny<n and not visited[nx][ny]: #만일 조건에 맞는다면
visited[nx][ny]=1 tmp=arr[nx][ny]
next=[t+1,nx,ny]
if tmp==0 or tmp==size: #암것도없거나 똑같은 사이즈면
que.append(next) #다음노드로
elif size>tmp: #상어가 더 크다면
heapq.heappush(heap,next) #heap에 들어가기
if heap: return heapq.heappop(heap) return -1
########################################### while True:
res=bfs(shark) if res==-1: #더이상먹을물고기가없으면 print(answer) #정답출력
exit() else: t,x,y=res #시간,x,y arr[x][y]=0
eat+=1 #먹은거 if eat==size: #크기만큼 먹었으면 size+=1 #크기증가
eat=0 #먹는거 초기화 answer+=t shark=[x,y]