BFS 미로의 최단거리 통로 질문입니다.

Question

1 0 0 0 0 1 1 0 0 이라는 board가 있다고 가정하겠습니다. (1,1)은 출발점이라 1로 표시했습니다. 큐의 현재 상태는 (1,1)입니다.(맨처음) 1 1 0 1 0 1 1 0 0 (1,1)을 큐에서 꺼내고 반복문을 돌면 큐의 상태는 (1,2), (2,1)이 될 것이고, board는 위와 같을것입니다. 1 1 1 1 1 1 1 0 0 (1,2)를 큐에서 꺼내고 반복문을 돌면 큐의 상태는 (2,1), (1,3), (2,2)가 될 것이고, board는 위와 같을것입니다. (1,3)과 (2,2)가 큐에 삽입되고 board상에서는 1로 처리되니까요 그런데 이렇게 되면, 현재는 (1,1) -> (1,2).. 의 방향으로 경로를 탐색하고 있지만 나중에 (1,1) -> (2,1) .. 의 방향으로 경로를 탐색할 때 이미, board[nx][ny]를 1로 바꿔버렸기 때문에 다른 방향으로 뻗어나가는 경로에 지장을 줄 수 있지 않나요??

김태원 · Answer

안녕하세요^^ 큐에 들어간 좌표는 이미 방문한 곳이기 때문에 체크를 하는 것이고, BFS는 이곳을 다시 방문할 필요가 없습니다. DFS가 한 번 간 곳을 다시 방문하는 백트랙킹이라면 BFS는 한 번 방문한 곳을 다시 방문하지 않는 레벨탐색방법입니다.