A. 문제설명
https://www.acmicpc.net/problem/16236
문제에 대한 자세한 설명은 링크 참조
1. N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 존재
2. 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동
3. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있음
4. 먹을 수 있는 물고기가 여러마리라면 거리 -> Y축 좌표 -> X축 좌표 기준으로 우선순위에 따라 선택
5. 물고기 다 먹고 먹을 게 없는 상황에서 걸린 시간 반환
B. 접근법
BFS + 정렬
처음에 시뮬레이션으로 풀어보려다가 실패 후 BFS + 정렬로 다시 풀게 되었다.
BFS는 상어의 각 위치마다 도달할 수 있는 먹이의 위치를 찾는 로직이고, 정렬은 모든 먹이의 위치를 구조체 배열에 넣었을 때 가장 가깝거나 좌측상단에 가까운 먹이를 찾기 위함이다.
이렇게 BFS -> 정렬로 가장 가까운 먹이 찾기, 반복하며 더이상 먹을 수 있는 먹이가 없을 때까지 반복하는 것이 전략
C. 풀이
1. 먹을 수 있는 물고기 없을 때까지 물고기 탐색 반복 진행
2. 물고기 탐색시 현재 상어의 위치에서 BFS 탐색, 주변 도달 가능한 물고기들에 대한 벡터 정보를 모음
3. 배열의 위치에서 더 큰 물고기는 못지나가고, 더 작은 물고기에 도달가능한 모든 좌표와 거리 정보를 벡터에 삽입
4. 이렇게 모은 벡터 정보는 FISH 구조체 벡터 fishVec에 들어가고, 거리 -> Y축 좌표 -> X축 좌표의 우선순위로 정렬
5. 이 중 가장 우선순위 높은 물고기 먹고 해당 위치로 상어 이동. 다시 1 반복
D. 내 코드
