DFS와 BFS

1. DFS/BFS

1. stack과 queue의 개념에 대해 잘 알고 있도록 하자.
   • stack은 First In Last Out 혹은 Last In First Out 구조이다.
   • queue는 First In First Out 구조이다.
   • queue는 기본 라이브러리 말고 collections 모듈에서 제공하는 deque를 활용하자.

2. Recursive 함수를 잘 사용하자.

   이때 recursive 함수의 느낌은 이런 것 같다. 어떤 멈춤 지점을 고려해서 그 곳에 return을 걸어 놓고, 함수들을 연속적으로 불러 한층씩 아래로 쌓는다. 그리고 멈춤 지점에서부터 역으로 한층씩 올라오면서 return에 값을 내놓는 느낌이랄까..! factorial의 예제를 들면,

    def factorial_recursive(n):
    # return 을 통해서 쫙 실행되고 찹찹찹 올라가는 느낌.
    if n <= 1 :
        return 1
    # n! = n * (n-1)!
   
    return n*factorial_recursive(n-1)
   

   위 함수에서 n=5라고 하면, 순서는 다음과 같이 전개 될 것이다. factorial_recursive(5) -> factorial_recursive(4) -> factorial_recursive(3) -> factorial_recursive(2) -> factorial_recursive(1) -> return 1

   n=1 일 때, return 1이 나오게 되고 역으로 올라가면서 return에 값을 미친다.
   return 1 -> return 2x1 = 2-> return 3x2 = 6 -> return 4x6 = 24 -> return 5x24 = 120

3. DFS는 Depth, First Search의 약자로써 가장 깊은 곳 부터 탐색하는 알고리즘이고, Stack 구조를 사용한다.
   • 깊게 들어가기 위해서 recursive 함수를 사용하게 된다.
4. BFS는 Breadth, First Search의 약자로써 가장 가까운 노드부터 탐색하는 알고리즘이고, Queue 구조를 사용한다.
   • 주변 탐색이므로 깊게 들어갈 필요가 없기 때문에, recursive 함수를 사용하지 않는다.
5. 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각해보려고 노력하자.