DFS(깊이 우선 탐색) 알고리즘

DFS는 대표적인 그래프 탐색 알고리즘 중 하나입니다.
탐색Search이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미합니다.

자바스크립트에서 dfs같은 그래프 문제를 해결할 때는 2차원 배열(리스트)로 그래프 표현합니다.
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데요.
2차원 배열로 그래프의 연결 관계를 표현하는 방식인 인접 행렬과
리스트로 그래프의 연결 관계를 표현하는 방식인 인접 리스트가 있습니다.

자바스크립트에서는 인접 리스트 표현 방식이 주로 사용됩니다.

DFS, 깊이 우선 탐색은 그래프나 트리에서 모든 노드를 한번씩 탐색하기위한 기본 방법입니다.
완전 탐색을 수행하는 가장 간단한 방법 중 하나이며, 스택(stack) 자료구조를 사용합니다.

DFS의 동작 방법

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

DFS는 완전 탐색이 목적인 경우 BFS보다 느린 경향이 있습니다.
그럼에도 구현 편리성 때문에 BFS 대신 사용하는 경우가 많습니다.

function dfs(graph, v, visited){
  visited[v]=true;
  console.log(v);

  for(let i of graph[v]){
    if(!visited[i]){
      dfs(graph, i, visited)
    }
  }
}

const 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);

위의 graph 배열을 그림으로 표현하면 다음과 같습니다.

깊이 우선 탐색의 사용 예시는 다음과 같습니다.

1. 더 짧은 코드 간결히 구현해야 하는 경우
2. queue 라이브러리 사용할 수 없는 경우
3. 트리의 순회, 점화식(이웃한 항들의 관계식) 구현 등 DFS(재귀 구조)에 특화된 문제인 경우
4. 두 노드를 잇는 경로가 하나만 존재하는, 트리에서의 최단 거리 탐색