문제 링크
https://www.acmicpc.net/problem/16236
🕒 Python 풀이시간: 25분
from collections import deque
dx=[0,0,-1,1]
dy=[-1,1,0,0]
n=int(input())
board=[]
babyShark_pos=[-1,-1]
for i in range(n):
tmp=list(map(int,input().split()))
for j in range(n):
if tmp[j]==9:
babyShark_pos[0],babyShark_pos[1]=i,j
tmp[j]=0
board.append(tmp)
babyShark_size=2
stack=0
def find_fishes():
q=deque()
q.append(tuple(babyShark_pos))
visited[babyShark_pos[0]][babyShark_pos[1]]=0
fishes=[]
while q:
x,y=q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if visited[nx][ny]!=-1:
continue
if board[nx][ny]>babyShark_size:
continue
visited[nx][ny]=visited[x][y]+1
q.append((nx,ny))
if 0<board[nx][ny]<babyShark_size:
fishes.append((visited[nx][ny],nx,ny))
return fishes
time=0
while True:
visited=[[-1]*n for _ in range(n)]
fishes=find_fishes()
fishes.sort(key=lambda x:(x[0],x[1],x[2]))
if len(fishes)==0:
break
else:
target=fishes[0]
time+=target[0]
babyShark_pos[0],babyShark_pos[1]=target[1],target[2]
board[target[1]][target[2]]=0
stack+=1
if stack==babyShark_size:
babyShark_size+=1
stack=0
print(time) 🐟 아기 상어의 먹이 사냥 🐟
아기 상어의 움직임을 시뮬레이션하는 문제이다. 상어의 처음 크기와 N*N칸에 있는 물고기들의 크기가 주어질 때, 상어는 자신보다 작은 물고기만 먹을 수 있고 자신보다 큰 물고기가 있는 길로는 지나갈 수 없다. 이러한 상황에서 상어의 움직임이 멈출 때, 즉 더 이상 먹을 수 있는 물고기가 없을 때까지의 시간을 구하는 것이다. 시간은 상어가 물고기를 먹으러 이동하는 칸수와 같다.
그렇기 때문에 상어가 먹을 수 있는 물고기를 찾는 것이 관건이다. 각 칸까지의 최단거리로 이동하고 모든 물고기를 파악해야 가장 윗쪽에 있고 가장 왼쪽에 있는 물고기를 찾을 수 있기 때문에 BFS 알고리즘으로 접근하였다. 현재 상어의 위치를 기준으로 BFS를 사용하여 모든 물고기를 찾아가되 각 칸까지의 거리를 visited로 기록하였고 현재 상어의 크기보다 클 경우 지나갈 수 없었다. 또한 마지막으로 만약 상어보다 크기가 작고 빈칸(0)이 아니라면 먹을 수 있는 물고기 리스트에 넣어준다. 이 리스트를 기준에 따라 정렬하였을 때, 가장 앞에 있는 물고기가 바로 먹을 물고기가 된다.
이제는 이동만 시켜주면 된다. 먹을 수 있는 물고기가 없다면 상어는 상황을 종료한다. 먹을 수 있는 물고기가 있다면 가장 앞에 있는 물고기가 있는 곳의 시간, 즉 visited 값만큼 시간을 더하고 상어를 해당 위치로 이동시켜준다. 해당 자리(board)에 있는 물고기는 사라진다. 그리고 크기만큼 먹었을 때, 상어의 크기가 커지기 때문에 stack으로 +1을 해준다. stack이 상어의 사이즈와 같아진다면 상어의 크기를 증가시키고 stack을 초기화한다.
이렇게 Python로 백준의 "아기 상어" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
