자료구조&알고리즘_BFS,DFS

BFS (너비 우선 탐색)

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 노드부터 탐색하는 알고리즘

BFS 특징

• Queue를 이용하여 구현
• 루트 노드부터 가까운 노드부터 탐색
• V가 정점의 수, E가 간선의 수 일때 BFS의 시간복잡도는 O(V+E)

DFS (깊이 우선 탐색)

그래프 탐색 알고리즘으로 최대한 깊은 노드부터 탐색하는 알고리즘

DFS 특징

• Stack을 이용하여 구현
• 루트 노드에서 깊은 노드부터 탐색
• V가 정점의 수, E가 간선의 수 일때 DFS의 시간복잡도는 O(V+E)

DFS 이진트리 순회

전위순회

작업순서 : 부모 노드 -> 왼쪽 자식노드 -> 오른쪽 자식노드

중위순회

작업순서 : 왼쪽 자식노드 -> 부모 노드 -> 오른쪽 자식노드

후위순회

작업순서 : 오른쪽 자식노드 -> 부모 노드 -> 왼쪽 자식노

코드구현

function solution(n) {
  const preOrderArr = [];
  const inOrderArr = [];
  const postOrderArr = [];

  function preOrder(v) {
    if (v > 7) {
      return;
    } else {
      preOrderArr.push(v);
      preOrder(v * 2);
      preOrder(v * 2 + 1);
    }
  }

  function inOrder(v) {
    if (v > 7) {
      return;
    } else {
      inOrder(v * 2);
      inOrderArr.push(v);
      inOrder(v * 2 + 1);
    }
  }

  function postOrder(v) {
    if (v > 7) {
      return;
    } else {
      postOrder(v * 2);
      postOrder(v * 2 + 1);
      postOrderArr.push(v);
    }
  }

  preOrder(n);
  inOrder(n);
  postOrder(n);

  console.log(preOrderArr);	// 1 2 4 5 3 6 7
  console.log(inOrderArr);	// 4 2 5 1 6 3 7
  console.log(postOrderArr);// 4 5 2 6 7 3 1
}

console.log(solution(1));

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스