djang   3년 전

BFS 탐색시 방향 우선순위로 해결할 수 없습니다.

현재 상태에서 상어가 잡아먹을 수 있는 모든 물고기를 조사하신 다음에 가장 거리가 짧고 위에 있고 왼쪽인 물고기를 찾으셔야 합니다.

BFS시 방향으로 하면 예제 입력 4번이 제대로 된 정답이 나오지 않습니다.

fbfbf1   3년 전

스포 당했네요..

djang   3년 전

앗 지울까요...?

fbfbf1   3년 전


문제를 아직 풀지는 않았지만 글과 제목만 보면

문제에서 요구하는 중요한 아이디어를 그대로 써놓으신 것 같아서

제목만 바꿔주시거나 삭제 하는게 좋을 것 같습니다.

stature_lee   3년 전

감삽니다 덕분에 고쳤습니다...

왜 안되나 해봤더니 방문 순서일 땐 현위치 기준으로 위쪽 행 오른쪽에 있는 값보다 같은 행 왼쪽 값이 먼저 선택되는 경우가 있네요.

sounhs2000   3년 전

감사합니다 ㅠㅠㅠ 반례를 도저히 못찾고 있었는데 함정이 있었네요... 덕분에 해결했습니다 감사합니다!

jennifer0606   2년 전

한가지 더 첨언하자면

"현재 상태에서 상어가 잡아먹을 수 있는 모든 물고기를 조사하신 다음에 가장 거리가 짧고 위에 있고 왼쪽인 물고기를 찾으셔야 합니다."

이때 먹을 수 있는 모든 물고기를 전수조사할 필요는 없고, 먹을 수 있는 물고기가 큐에서 처음 pop 됐을 때 큐에 남은 물고기중 가장 위, 왼쪽에 있는 물고기를 찾으면 됩니다! 그러면 먹을 수 있는 물고기중 가장 가까운 물고기들만 조사하게 되는것과 같은 효과를 볼 수 있어요!

댓글을 작성하려면 로그인해야 합니다.