스포 당했네요..
16236번 - 아기 상어
감삽니다 덕분에 고쳤습니다...
왜 안되나 해봤더니 방문 순서일 땐 현위치 기준으로 위쪽 행 오른쪽에 있는 값보다 같은 행 왼쪽 값이 먼저 선택되는 경우가 있네요.
감사합니다 ㅠㅠㅠ 반례를 도저히 못찾고 있었는데 함정이 있었네요... 덕분에 해결했습니다 감사합니다!
한가지 더 첨언하자면
"현재 상태에서 상어가 잡아먹을 수 있는 모든 물고기를 조사하신 다음에 가장 거리가 짧고 위에 있고 왼쪽인 물고기를 찾으셔야 합니다."
이때 먹을 수 있는 모든 물고기를 전수조사할 필요는 없고, 먹을 수 있는 물고기가 큐에서 처음 pop 됐을 때 큐에 남은 물고기중 가장 위, 왼쪽에 있는 물고기를 찾으면 됩니다! 그러면 먹을 수 있는 물고기중 가장 가까운 물고기들만 조사하게 되는것과 같은 효과를 볼 수 있어요!
댓글을 작성하려면 로그인해야 합니다.
djang 3년 전 1
BFS 탐색시 방향 우선순위로 해결할 수 없습니다.
현재 상태에서 상어가 잡아먹을 수 있는 모든 물고기를 조사하신 다음에 가장 거리가 짧고 위에 있고 왼쪽인 물고기를 찾으셔야 합니다.
BFS시 방향으로 하면 예제 입력 4번이 제대로 된 정답이 나오지 않습니다.