백준 #16236 아기상어 - bfs 탐색 순서만으로는 해결할 수 없는 우선순위가 있다!

아기상어의 선택 조건 :

1. 거리가 가장 가까운 물고기

2. 그 중에서 가장 위쪽 물고기

3. 그 중에서 가장 왼쪽 물고기

​

bfs에서 상, 좌, 우, 하 순서로 큐잉했는데 거리가 2 이상인 경우부터 문제가 생긴다.

거리 2부터 큐에 담기는 순서

삐뽀삐뽀! 5번 부터 문제 발생!!

​

해결책 1. 처음으로 먹을 수 있는 물고기가 pop 됐을때, 남은 큐를 다 뒤져서 조건에 맞는 물고기를 찾는다.

-> 먹을 수 있는 물고기가 처음 pop 됐을 때, 같은 거리의 물고기가 이미 모두 큐에 들어가 있을 것인가? YES!

해결책 2. 먹을 수 있는 물고기 전수조사 후 최적 물고기 찾기.

-> bfs 돌리는 의미가 퇴색됨

​

위는 해결책 1로 돌린 경우, 아래는 해결책2 전수조사 한 케이스다. 꽤 시간차가 난다!

n단계가 bfs 큐에서 팝될때는 이미 이전 단계를 모두 bfs 돈 이후이다.

즉 n 단계가 큐에서 처음 팝 된 경우 큐에는 오로지 n 단계 노드들만 들어있을 것이라고 예상할 수 있다. 추후 다른 문제 풀 때 이런 접근이 도움이 될지도!