[Algorithm] DFS 알고리즘

DFS와 BFS

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
• 대표적인 그래프 탐색 알고리즘으로는 DFS, BFS가 있다.

Stack 자료 구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

let stack = [];

// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.push(5);
stack.push(2);
stack.push(3);
stack.push(7);
stack.pop();
stack.push(1);
stack.push(4);
stack.pop();

let reversed = stack.slice().reverse();
console.log(reversed); // 최상단 원소부터 출력
console.log(stack);

// output
[1, 3, 2, 5]
[5, 2, 3, 1]

그래프의 표현

• 2차원 배열(리스트)로 그래프를 표현한다.

1 ---- 2
| \    |
|  \   |
|   \  |
3 ---- 5
|    /
|   /
|  /
4 

• 인접 리스트

Node	Connected Nodes
1	2, 3
2	1, 5
3	1, 4, 5
4	3, 5
5	2, 3, 4

깊이 우선 탐색(DFS)란?

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

DFS 기본 동작 방식

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

DFS 구현 특징

• DFS를 실제로 구현할때는 스택 혹은 재귀 함수를 이용한다.
  -> 재귀함수는 내부적으로 스택과 동일한 동작 원리를 가지므로 구현의 편리성이 존재한다.
• 완전 탐색을 목적으로 하는 경우, 탐색 속도가 BFS보다 느린 경향이 있다.
• 그럼에도 구현의 편리성 때문에 BFS 대신에 사용하는 경우 또한 많다.

DFS 사용 예시

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

DFS 소스 코드 예시

function dfs(graph, v, visited) {
  //현재 노드를 방문 처리 
  visited[v] = true;
  console.log(v);
  for(i of graph[v]) {
    if(!visited[i]) dfs(graph, i, visited);
  }
}

DFS를 활용한 완전 탐색

• 흔히 DFS는 모든 노드를 [완전탐색]하기 위핸 방법으로 사용됨
• 완전 탐색 알고리즘에서는 기본적으로 각 노드 및 간선에 대하여 한번씩 확인하도록 한다.
• DFS를 응용하여 모든 경우의 수를 계산하기 위핸 백트래킹 알고리즘으로 사용할 수 있다.
  -> 백트래킹에 비하여 기본적인 형태의 DFS는 그 코드 예시가 간단하다.