Search

아기 상어

문제 : 아기 상어

16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
https://www.acmicpc.net/problem/16236

풀이

해결에 필요한 핵심 아이디어: BFS

•
물고기 잡아 먹기
◦
BFS를 활용하여 도착할 수 있는 공간의 최단 거리 구하기
▪
일반적인 BFS 알고리즘에 상어 크기를 넘지 않는 물고기가 있는 경우에만 탐색 가능한 조건 추가
◦
잡아 먹을 수 있는 물고기가 있는 동안 반복해서 물고기 잡아 먹기
▪
먹을 수 있는 물고기 중 최단 거리의 위치와 거리 반환하는 함수 구현
▪
상어의 위치, 사이즈 갱신
◦
더 이상 잡아 먹을 수 있는 물고기가 없는 경우엔 잡아 먹은 시간을 반환
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.

Made with