JS 100제

- 문제71

답안

const graph = {
  'A': ['E', 'C', 'B'],
  'B': ['A'],
  'C': ['A'],
  'D': ['E','F'],
  'E': ['D', 'A'],
  'F': ['D'],
};


function dfs(graph, start){
  let visited = [];
  let stack = [start];

  while (stack.length !== 0){
    let n = stack.pop();
    if (!visited.includes(n)){
      visited.push(n);
      let sub = graph[n].filter(x => !visited.includes(x));
      for(let i of sub) {
        stack.push(i);
      }
    }
  }
  return visited;
}


console.log(dfs(graph, 'E'));

깊이 우선 탐색(DFS, Depth First Search)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘입니다. 이러한 깊이 우선 탐색은 맹목적으로 각 노드를 탐색할 때 주로 사용됩니다. 너비 우선 탐색에서는 큐(Queue)가 사용되었다면 깊이 우선 탐색(Depth First Search)에 스택(stack)이 사용된다. 더불어 사실 스택을 사용하지 않아도 구현이 가능하다는 특징이 있다. 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문이다.

방문했던 곳을 visited 배열에 저장하고 방문한 노드에 자식 노드들을 stack에 쌓고 자식 노드들을 방문하고 visited에 저장하고 반복하여 전체를 탐색하게 하는 로직.

reference
https://blog.naver.com/ndb796/221230945092

<출처-JS 100제 문제71>
https://www.notion.so/71-540f7cca5b6b4693a985c3bc370778b9