[Javascript] (DFS) 깊이 우선 탐색 - 전위 순회, 중위 순회, 후위 순회

DFS : 깊이 우선 탐색 (한 방향으로 쭉 깊게 들어감)

재귀를 이해했다면 DFS를 이해할 차례다.

DFS를 이해하기 위해 이진 트리의 순회를 먼저 해보자. 이진트리 순회 방식에는 3가지가 있다.

1. 전위 순회
2. 중위 순회
3. 후위 순회

이름이 굉장히 구린데, 부모노드 (정점, vertex)의 순서가 앞에 있냐, 중간에 있냐, 뒤에 있냐 로 해석하면 이해가 된다.

코드로 설명하자.

전위 순회

function solution(n) {
  // 전위 순회 (부모 먼저 => 왼 오)
  function DFS(v) {
    if (v > 7) return;

    console.log(v);
    DFS(v * 2);
    DFS(v * 2 + 1);
  }
  DFS(n);
}

console.log(solution(1));

function solution(n) {
    // 중위 순회
  function DFS(v) {
    if (v > 7) return;

    DFS(v * 2);
    console.log(v);
    DFS(v * 2 + 1);
  }
  DFS(n);
}

console.log(solution(1));

function solution(n) {
  // 후위 순회
  function DFS(v) {
    if (v > 7) return;

    DFS(v * 2);
    DFS(v * 2 + 1);
    console.log(v);
  }
  DFS(n);
}

console.log(solution(1));

위 세가지 코드가 같아 보이겠지만, 콘솔로그의 위치가 다르다.

신기하게도 vertex를 앞에 찍으면 전위순회, 중간에 찍으면 중위순회, 뒤에 찍으면 후위순회가 된다.

나처럼 머리에 한계로 이해가 안되는 사람은 직접 콜스택을 그리면서 콘솔로그를 손으로 찍어보면 알게 된다.