[16236] 아기 상어

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

16236번: 아기 상어

그래프 탐색 문제다. 너비 우선 탐색으로 풀었다. 상어의 움직임에 대해 오래 고민했던 문제다.

 

풀이

상, 좌, 우, 하 순서로 너비 우선 탐색을 수행한다. 빈 곳이거나 같은 사이즈의 물고기를 만난다면 큐에 담아 이동을 수행, 자신보다 작은 사이즈의 물고기를 만나면 해당 좌표를 다른 배열에 저장하였다.

탐색이 끝난 뒤 문제의 조건에 맞게 먹을 수 있는 물고기가 담긴 배열을 시간, x좌표, y좌표 순으로 정렬한 뒤 가장 가까운 좌표로 이동하여 해당 물고기를 먹으면 된다. 처음에는 이러한 정렬 없이 먹을 수 있는 물고기를 만나면 바로 먹어버리고 탐색을 종료했는데, 같은 거리에 있는 먹을 수 있는 물고기에 대한 조건이 안 맞아 오답이 나왔다.

탐색 함수는 상어가 이동한 좌표와 걸린 시간을 반환하게 하였다. 상어의 좌표에 이동이 없는 경우 먹을 수 있는 물고기가 없는 것으로 판단하여 반목문을 빠져나오는 것으로 코드를 작성했다.

 

정답 코드