TIL(20.03.30) DFS,BFS,Backtracking

오늘은 DFS와 BFS, Backtracking에 대해 알아보았습니다.

< 오늘 배운 것 >😆

• DFS

• BFS

• Backtracking

1. DFS

What is DFS??

DFS는 (Depth first searching)으로 깊이 우선 탐색의 줄임말입니다. 깊이 우선 탐색이란 위의 그림과 같이 아래로 내려가면서 탐색을 하는 탐색의 방법입니다. DFS는 재귀함수를 사용하여 탐색을 진행하는데 이러한 점에 있어서 백트래킹이라는 개념이 나옵니다.

2. BFS

What is BFS??

BFS는 (Breath first searching)으로 넓이 우선 탐색의 줄임말입니다. BFS는 queue를 사용하여 탐색을 진행 하는데 psuedoCode를 통해 어떻게 진행되는지 알아보겠습니다.

BFS psuedocode

BFS(root)
  Pre: root is the node of the BST
  Post: the nodes in the BST have been visited in breadth first order
  q ← queue
  while root = ø 
    yield root.value
    if root.left = ø
      q.enqueue(root.left)
    end if
    if root.right = ø
      q.enqueue(root.right)
    end if
    if !q.isEmpty()
      root ← q.dequeue()
    else
      root ← ø
    end if
  end while
end BFS

3. Backtracking

What is Backtracking??

백 트래킹은 말 그대로 번역을 하면 되추적입니다. 되추적이라는 말만 봐서는 알 수가 없는데요... 손 쉽게 얘기해서 자신이 원하는 조건을 충족하지 못한다면 다시 전 조건으로 돌아가 실행을 한다라고 표현 할 수 있을 것 같습니다. 말로 풀어서는 제대로 이해하기가 힘드니 백트래킹의 예제를 가지고 접근 해보겠습니다.

트리의 예제를 가져와 보았습니다. 여기서 위의 procedure조건을 걸어주고 조건을 만족시키지 않는다면 다시 backtracking 다시 되돌아가 다음 노드를 탐색하게 됩니다.