다른 게시물들 보시면 시작지점을 방문처리를 안했거나, 큐에넣기전 방문체크하지않고 큐에서 꺼낼때 방문체크 하시면 시간초과가 난다고 되어있습니다.

이 케이스를 빼고 무한루프에 걸리는 경우도 시간초과가 됩니다.

두괄식으로 반례부터 드립니다.

6
1 2 0 3 1 6
1 0 5 0 0 0
1 0 2 0 2 0
0 1 4 0 2 5
6 6 3 0 3 3
4 9 6 0 2 2

이 반례는 하단에 반례맛집 게시글에서 갖고온 데이터입니다.

데이터를 보시면 상어가 물고기에 둘러쌓여 움직이지 못합니다. 따라서 먹잇감이 있지만 먹지 못하는 경우입니다.

이 반례에 걸리는 경우는 종료조건을 bfs로 더이상 찾을 수 있는게 없는경우로 하지 않고 맵을 전체순회하며 더이상 먹을게 있는지 없는지를 확인했기 때문에 발생합니다.

이건 다른문제에서도 흔히 접하는 에러인데 bfs를 통해 맵을 체크하는경우의 문제유형은 여러가지가 있지만

1) 맵에서 특정 위치를 도착지로 최단거리 찾기

2) 모든 맵을 검사하기

를 위해 bfs를 사용합니다. 이때 1)의 유형에서 bfs를 중단하는 경우는 두가지가 있습니다.

도착지를 찾는경우와 도착지를 찾지 못하는 경우 입니다.

도착지를 찾는다면 bfs를 바로 종료시키겠지만 도착지를 찾지 못한다면 is.empty()에 걸려서 종료될것입니다. 이 두가지케이스를 구분해야 한다는부분만 기억하면 될것같습니다.