백준 16236. 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

공간의 크기 N이 최대 20으로 매우 작기 때문에 매번 아기상어보다 작으면서 가까운 물고기를 찾으면 된다.

좌측상단부터 우측하단으로 탐색하면서 아기상어보다 크기가 작은 물고기의 거리를 bfs 알고리즘으로 구하고,  가장 가까운 물고기를 먹는다.

 

탐색을 좌측상단에서 우측하단으로 진행하면 상어가 어디로 이동할지 결정하는 조건중 

 

• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

위 마지막 조건을 자동으로 충족한다.