다시 방문하는 칸은 시작점 하나고 그 이웃은 이미 방문했으므로 반례가 안 생길 것으로 보이는데, 혹시 다른 부분의 로직이 다른 게 아닐까요?
16236번 - 아기 상어
다시 방문하는 칸은 시작점 하나고 그 이웃은 이미 방문했으므로 반례가 안 생길 것으로 보이는데, 혹시 다른 부분의 로직이 다른 게 아닐까요?
말씀하신 대로 주석으로 바꿔서 내면 정답 판정됩니다. https://www.acmicpc.net/source...
댓글을 작성하려면 로그인해야 합니다.
cty0121 7달 전
먹을 수 있는 물고기를 찾는 과정에서 visited를 0으로 초기화하고 상어 시작 위치도 0으로 해서 시작했습니다. 중간에 나아갈 수 있는 방향을 체크 하는 부분에서 visited[rx][ry]!=0을 기준으로 찾았습니다.간단하게 하자면 처음에는 주석처리된 부분으로 해서 풀었습니다. 예제는 6개 모두 통과해서 맞았구나 했는데 2%에서 틀렸습니다.
왜일까 하고 생각해봤는데 상어 시작위치도 방문 안된 걸로 처리해서 좀 꼬였나 해서 -1을 기준으로 풀었더니 맞았습니다.
제 논리는 상어 시작위치도 방문안한걸로 처리해서 다시 bfs를 위한 큐에 들어갔다고 해도 어처피 visited에는 거리가 저장되고 있기 때문에 긴 거리는 알아서 넘어가질 것이고 따라서 원래 틀렸습니다가 나왔을때도 예제 6개가 맞았다고 생각합니다. 논리적 허점이 없는건 -1로 visited를 초기화해서 푸는 것이 맞지만 0으로 초기화해도 정답은 나와야 하는 것 아닌가요?
답변 부탁드립니다.