DFS 와 BFS의 방문처리 시점은 왜 다를까??

DFS(깊이 우선 탐색)은 재귀함수, STACK을 이용하여 구현하고 

BFS(넓이 우선 탐색)은 QUEUE를 이용하여 구현한다. 

기계적으로 코드를 구현하다보니 문득 궁금한점이 생겼다. 

왜 두 탐색방법의 방문처리시점이 다를까? 

 

이 궁금증을 이전에 제대로 해결하지 않은채 코테나 알고리즘 문제를 풀다 

방문처리 시점을 헷갈려 시간을 낭비하게 되는 경우가 있었다. 

 

이는 STACK과 QUEUE와 함께 dfs bfs의 근본적인 동작방식을

제대로 이해하는데도 큰 도움이 된다고 생각하여 정리해보겠다.

 

우선 dfs의 방문처리 시점은 실제로 그 지점을 방문한 직후에 처리를 한다.

bfs처럼 이전에 하면 안되는 이유가 뭘까?

dfs는 범위내에있고 방문한적이 없다면 갈수있을때까지 파고든다. 

즉, 방문가능지역 검사에서 만난 순서와 실제 탐색지역의 순서는 별개이다. 

 

그런데 만약 방문가능지역을 검사하는 과정에서(보통 for문을 통해 사방탐색) 방문처리를 미리 하면 어떻게 될까?

방문처리를 미리 한다고 해서 방문하지 않는곳이 생기지는 않는다.

그러나 스택을 이용하여 dfs를 구현할때 visit처리를 미리 해준다면 방문순서를 좌표상에 표시해야할때 

문제가 생긴다. 실제 방문순서와 방문가능지역 탐색순서가 다르기 때문이다.

 

 

그렇다면 bfs의 경우는 왜 방문처리를 미리 해주는것일까?

bfs는 dfs와 달리 방문가능지역 검사에서 만난 순서와 실제 탐색지역의 순서가 일치한다. 

즉, 탐색을 하며 방문가능지역 후보들을 만난다면 모두 큐에 넣고 순서대로 이용하기 때문이다. 

 

그런데 만약 방문처리를 미리해주지 않고 직접 방문했을때 해준다면 어떻게 될까? 

 

결론은 상관없다.

 

큐를 이용하여 다음 방문할곳을 정하기 때문에 방문가능 탐색순서와 실제 탐색순서가 일치하기 때문이다. 

그러나 이 경우에도 방문순서를 좌표상에서 알아야 하거나 정확하게 한번만

방문해야 오류가 없는 상황인 경우에는 문제가 발생할 수 있다. 

또 큐에 동일한 좌표가 뒤에 또 들어오는 경우가 있어 효율성 측면에서는 문제가 될 수 있다.  

 

 

만약 방문 순서대로 좌표에 번호를 표시한다고 하면, 중복되어 큐에 들어가는 좌표에서는 

마지막 값이 이전값들을 덮어 쓰게되므로 의도하지 않은 값이 출력된다.