hds1630   2년 전

Point 좌표 이동하면서 벽을 부쉈는지 안부쉈는지는 check변수로 판단하며 dfs로 구현했는데 반례 좀 찾아주세요...

djm03178   2년 전

반례를 찾는다고 해결할 정도의 코드가 아닙니다. 근본적으로 풀이가 틀렸습니다.

  1. 최단 거리는 DFS로 풀 수 없습니다. 어떤 칸에 처음 도달했을 때의 거리가, 다른 경로를 통해 도달한 거리보다 짧다는 보장이 있나요? 최단 거리는 무조건 BFS입니다.
  2. 한 방향에 벽이 있어서 부수고 check를 true로 바꿨습니다. 다른 방향을 봤는데 벽이 없습니다. 그런데도 check는 여전히 true인 상태로 나아가야 할까요?

hds1630   2년 전

감사합니다. BFS로 바꿔서 고민해보겠습니다!

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