[BFS / 알고리즘] BFS에서 방문처리가 의미하는 것

BFS 방문 처리

• BFS의 방문 처리는 방문을 한 곳을 체크하는 것이 아니라 방문할 예정인 곳을 체크하는 방식이다.
• BFS를 풀 때 Queue를 보통 사용하게 되는데, 방문 체크를 Queue에서 데이터를 뽑을 때 방문 체크를 하는 것이 아닌, Queue에 집어넣을 때 방문체크를 하게 된다.
  • 방문 한 곳을 체크한 경우, 방문 하진 않았지만 방문할 예정인 곳을 다른 곳에서도 접근 가능할 때 반복해서 탐색하는 경우가 생길 수 있다.
  • 하지만 방문할 예정일 때 이를 체크한다면 이런 경우를 없앨 수 있다.
• 따라서 방문 한 곳 을 체크한다는 말은 틀린 말이고 방문 할 곳 을 체크하는 것이 적절한 말이다.

 

예제