DFS,BFS 그리고 Backtracking

깊이 우선 탐색(DFS, Depth-First Search)

: 트리 자료구조에서 많이 사용되어지는 탐색방법이다.
루트 노드(혹은 다른 임의의 노드)에서 그 자식의 노드들을 먼저 완벽하게 탐색한다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리지만, 이 방법을 사용하면 모든 노드를 방문 할 수 있다.

DFS는 재귀를 통해서 구현할 수 도 있다. 이 재귀를 통해서 어제 오늘 힘들게 N-Queens 문제를 이해하고 풀 수 있었다.

그림으로 좀 더 자세히 알아보자

이 그림은 루트 노드 1번이 호출 되었을때이다. 이 그림에 오른쪽은 스택을 표현한것이다. 1번이 호출되면 1번은 스택에 쌓이게된다.

이 다음은 자식을 둘러 보게된다. 2번 자식을 먼저 보았고, 2번이 스택으로 쌓인것을 볼 수 있다.

이 다음은 당연히 3번 이 스택에 쌓이게 된다. 그러나 3번이 더 이상 자식이 없다. 그렇게 되면 3번 스택은 없어 지게되고, 2번 스택을 다시 확인한다. 2번도 순회할 자식이없기때문에 2번 스택도 지울 수 있다. 그 결과 아래의 사진과 같다.

2번과 3번 자식이 없기때문에, 1번 스택만 남았고, 1번의 또 다른 자식인 4번으로 넘어가서 4번 스택이 1번 스택 위에 쌓이게 된다.

그 다음은 위의 과정을 반복하여 5번 그리고 6번이 스택에 쌓인다.

6번에서 자식이 없어서 6번 스택이 사라지고, 5번 스택으로 순회하지만 5번도 자식이 없어서 5번 스택도 사라진다. 그래서 5번 밑에 쌓여있는 4번 스택에서 5번을 이미 순회했으니 다른 자식인 7번을 순회하고, 7번 스택이 쌓이게 된다.

이 모든 과정을 또 반복하면, 아래와 같은 그림으로 끝낼 수 있다.

너비 우선 탐색(BFS, Breadth-First Search)

: BFS방법은 전체를 탐색하는것 역시 DFS와 같지만, 인접한 노드들을 차례대로 방문하도록 구현한다는 점이다. 즉 같은 레벨의 노드들을 먼저 방문하는것이다. 이 상황에서는 스택을 사용하기보다는 큐를 사용하여 구현할 수 있다.

BFS로 queue구현하기.

: 사실 이 코드는 내가 적은것은 아니다. 우리 코드 스테이츠의 킹갓민철님께서 템플릿처럼 사용하면된다고 코드를 작성하면서 설명해주셨다. 이해하고 외우면 좋을것 같다.

function bfs() {
  let Q = [
    [0, 0],
    [0, 1],
    [0, 2],
    [0, 3],
  ];
  function enQ(ele) {
    Q.push(ele)
  }
  function deQ() {
    let head = Q[0];
    Q = Q.slice(1);
    return head;
  }
  // 4 X 4
  while (Q.length > 0) {
    // [0, 0]
    let choice = deQ();
    // [0, 1], [0, 2], [0, 3],
    let row = choice[0];
    let col = choice[1];
    for (let col = 0; col < N; col++){
      if (map[row + 1][col]에 놓을 수 있냐?) {
        enQ([row + 1, col])
      }
    }
  }
}

좀 더 자세히 알아보기

BackTracking

: