mintuchel   1년 전

BFS로 풀었고, 위쪽 > 왼쪽 > 오른쪽 > 아래쪽 순으로 움직이도록 dy dx 설정했습니다.

int dy[4] = {-1, 0, 0, 1};

int dx[4] = {0, -1, 1, 0};

이렇게 놓고 BFS로 돌렸고, 먹을 수 있는 물고기가 나오면 바로 탐색을 종료했습니다.

하지만 다른 사람들 코드를 보니 BFS 탐색을 통해 먹을 수 있는 물고기들을 list에 저장한 후,

다시 우선순위를 판단하여 먹을 수 있는 물고기들 중 우선순위가 가장 높은 물고기를 탐색하더군요.

BFS로 돌린 후, 최초로 먹을 수 있는 물고기가 나오면 왜 탐색을 바로 종료하면 안되는건가요??

가지 못하는 칸(자신보다 큰 물고기가 존재하는 칸)이 존재하여 돌아간다 하더라도, BFS 특성 상 최단경로를 보장하니,

따로 먹을 수 있는 물고기들을 저장한 후, 우선순위를 판단할 필요가 없지 않나요??

너무 궁금합니다.

고수님들 알려주시면 정말 감사하겠습니다.

zenith82114   1년 전

예제 4번이 반례입니다.

mmang   1년 전

해당 순서로 움직이더라도 올바른 물고기를 찾지 못하는 경우 입니다.
(1,3)에 있는 가장 위인 물고기를 먹어야 하나, 가장 먼저 만나는(3,1)에 있는 물고기를 먹게 됩니다.

먼저(2,2)에서 queue에 (2,1),(2,3)을 넣고,
(2,1)을 꺼낸 후 (3, 1)에 있는 물고기를 발견하고 먹게 됩니다.

mintuchel   1년 전

오 이렇게 쉬운 반례가 있었다니... 엉뚱한 반례에서 안되는 이유를 찾으려고 했네요. 감사합니다!!

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