DFS vs BFS

DFS와 BFS는 data structure때 그래프와 트리를 비교하면서 정리한 바 있다.
자세한 내용은 DFS와 BFS 여기를 참고하길 바란다.
그래도 간략하게 정의와 비교 그림만 알아보고 가자.

DFS의 정의(깊이 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법으로 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

BFS의 정의(너비 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.

DFS와 BFS의 원리 비교도

Backtracking(되추적)이란?

유망하지 않으면 배제를 하고 부모노드로 되돌아가면서 풀이 시간을 단축시키는 전략이다.

Backtracking의 원리와 그 설명도

1. 깊이 우선 탐색법을 시행한다.
2. 어떤 노드의 유망성을 검사한다.
3. 그 노드가 유망하지 않으면 가지치기를 하여 배제시킨다.
4. 가지치기를 한 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색하여 풀이시간을 단축시킨다.

Backtracking 용어정리

유망하다(promising) : 답이 될 가능성이 있다.
가지치기(pruning) : 유망하지 않은 노드(답이 될 가능성이 없는)는 더 이상 가지 않고 다음 노드를 검색하는 것

Backtracking 코드로 보는 예시

오피스 아워때 수업한 코드를 살짝 바꿔서 예시로 들겠다.

let code = ['A', 'B', 'C'];
// find all permutations

// but what if u want to find where B cant sit in the middle seat?
// backtrack

let result1 = [];
function permutation(usedArray, unusedArray) {
  if (usedArray.length === 3) {
    return result1.push(usedArray);
  }

  for (let i = 0; i < unusedArray.length; i++) {
    permutation(
      usedArray.concat(unusedArray[i]),
      unusedArray.filter((el, idx) => i !== idx)
    );
  }
}

permutation([], code);
console.log(result1);

let result2 = [];
function backtrackingPermutation(usedArray, unusedArray) {
  if (usedArray[1] === 'A' || usedArray[1] === 'B') {
    return;
  }

  if (usedArray.length === 3) {
    return result2.push(usedArray);
  }

  for (let i = 0; i < unusedArray.length; i++) {
    backtrackingPermutation(
      usedArray.concat(unusedArray[i]),
      unusedArray.filter((el, idx) => i !== idx)
    );
  }
}

backtrackingPermutation([], code);
console.log(result2);