16236번 - 아기 상어
BFS로 풀었고, 위쪽 > 왼쪽 > 오른쪽 > 아래쪽 순으로 움직이도록 dy dx 설정했습니다.
int dy[4] = {-1, 0, 0, 1};
int dx[4] = {0, -1, 1, 0};
이렇게 놓고 BFS로 돌렸고, 먹을 수 있는 물고기가 나오면 바로 탐색을 종료했습니다.
하지만 다른 사람들 코드를 보니 BFS 탐색을 통해 먹을 수 있는 물고기들을 list에 저장한 후,
다시 우선순위를 판단하여 먹을 수 있는 물고기들 중 우선순위가 가장 높은 물고기를 탐색하더군요.
BFS로 돌린 후, 최초로 먹을 수 있는 물고기가 나오면 왜 탐색을 바로 종료하면 안되는건가요??
가지 못하는 칸(자신보다 큰 물고기가 존재하는 칸)이 존재하여 돌아간다 하더라도, BFS 특성 상 최단경로를 보장하니,
따로 먹을 수 있는 물고기들을 저장한 후, 우선순위를 판단할 필요가 없지 않나요??
너무 궁금합니다.
고수님들 알려주시면 정말 감사하겠습니다.
해당 순서로 움직이더라도 올바른 물고기를 찾지 못하는 경우 입니다.(1,3)에 있는 가장 위인 물고기를 먹어야 하나, 가장 먼저 만나는(3,1)에 있는 물고기를 먹게 됩니다.
먼저(2,2)에서 queue에 (2,1),(2,3)을 넣고,(2,1)을 꺼낸 후 (3, 1)에 있는 물고기를 발견하고 먹게 됩니다.
오 이렇게 쉬운 반례가 있었다니... 엉뚱한 반례에서 안되는 이유를 찾으려고 했네요. 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
mintuchel 1년 전
BFS로 풀었고, 위쪽 > 왼쪽 > 오른쪽 > 아래쪽 순으로 움직이도록 dy dx 설정했습니다.
int dy[4] = {-1, 0, 0, 1};int dx[4] = {0, -1, 1, 0};이렇게 놓고 BFS로 돌렸고, 먹을 수 있는 물고기가 나오면 바로 탐색을 종료했습니다.
하지만 다른 사람들 코드를 보니 BFS 탐색을 통해 먹을 수 있는 물고기들을 list에 저장한 후,
다시 우선순위를 판단하여 먹을 수 있는 물고기들 중 우선순위가 가장 높은 물고기를 탐색하더군요.
BFS로 돌린 후, 최초로 먹을 수 있는 물고기가 나오면 왜 탐색을 바로 종료하면 안되는건가요??
가지 못하는 칸(자신보다 큰 물고기가 존재하는 칸)이 존재하여 돌아간다 하더라도, BFS 특성 상 최단경로를 보장하니,
따로 먹을 수 있는 물고기들을 저장한 후, 우선순위를 판단할 필요가 없지 않나요??
너무 궁금합니다.
고수님들 알려주시면 정말 감사하겠습니다.