Argorithm 공부 : DFS와 BFS

DFS란?

• 깊이 우선 탐색
  1. 자신에게 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다.
  2. 이동한 노드에서 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다.
  3. 이렇게 계속 내려가다가 자식 노드가 없는 노드를 찾는다.
  4. 다시 부모 노드로 이동하여 새로운 자식 노드를 찾는다.
  5. 또 자식노드가 없으면 다시 부모노드로 이동하여 위의 순서를 반복한다.
• 완전탐색 중 한 방법 - 위의 순서를 보면 모든 노드를 체크하는 것을 볼 수 있다.
• DFS에서 발전된 알고리즘 : 백트레킹
  • 백트레킹은 DFS 방식을 하면서 조건을 추가한다.
  • 한 노드가 조건에 맞지 않으면 밑의 자식노드 또한 조건에 맞지 않으므로 다시 부모노드로 돌아간다.
  • DFS보다 훨씬 시간을 줄일 수 있다.

DFS를 이해하기 위해서는 그림을 보면 쉽다.

밑의 그림은 노드 탐색할 때, 순서를 나타낸 것이다.

 

BFS란?

• 너비 우선 탐색
  1. 자신에게 연결되어 있는 여러 노드 중 하나를 골라 그 노드로 이동한다.
  2. 다시 부모 노드로 이동하여 여러 노드 중 탐색하지 못한 노드를 탐색한다.
  3. 자식 노드의 탐색이 다 끝나면 처음 탐색했던 자식 노드의 자식 노드들을 탐색한다.
  4. 자식노드의 자식노드들을 모두 탐색하면 다시 부모노드로 돌아가 다음 자식노드의 자식노드들을 탐색한다.
  5. 위의 순서를 반복한다.
• 완전탐색 중 한 방법 - 위의 순서를 보면 모든 노드를 체크하는 것을 볼 수 있다.
• 트리의 깊이가 너무 깊을 때, DFS를 사용하면 시간을 너무 낭비하는 경향이 있다.
• 너비 우선탐색은 깊이가 너무 깊은 트리의 얕은 깊이를 모두 탐색할 때 좋은 알고리즘이다.

BFS 또한 이해하기 위해서는 그림을 보면 쉽다.

밑의 그림은 노드 탐색할 때, 순서를 나타낸 것이다.