DFS(깊이 우선 탐색)

1. DFS(깊이 우선 탐색)이란?

(1) 개념과 특징

• 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법
• 완전 탐색을 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나
• 스택(stack) 자료 구조를 사용한다

(2) 동작 방식

• 시작 노드를 스택에 넣고 방문 처리함
• 스택에 마지막으로 들어온 노드에 방문하지 않은 인접 노드가 있는 지 확인한다.
• 있다면 방문하지 않은 인접 노드를 스택에 삽입하고 방문 처리한다.
• 없다면 현재 노드(스택에 마지막으로 들어온 노드)를 스택에서 추출한다.
• 이 과정을 더이상 반복할 수 없을 때 까지 반복한다.

(3) 구현 특징

• 완전 탐색을 목적으로 하는 경우, 탐색 속도가 BFS보다 느린 경향이 있다.
• 구현이 편리함

(4) 사용 예시

• 트리의 순회, 점화식 구현 등
• 트리에서 최단 거리 탐색

(5) 소스 코드

function DFS(graph, v, visited){
  //현재 노드를 방문 처리
  visited[v]=true;
  console.log(v);
  //현재 노드와 연결된 다른 노드들을 재귀적으로 방문
  for(let i of graph[v]){
    if(!visited[i]){
      DFS(graph,i,visited)
    }
  }
}


let graph=[[],[2,3,4],[1],[1,5,6],[1,7],[3,8],[3],[4],[5]]  
let visited=Array(9).fill(false)

DFS(graph, 1, visited)