- DFS (Depth-First-Search)

DFS는 깊이 우선 탐색이라고 하고 말그대로 깊이를 우선적으로 탐색하는 알고리즘이다.

깊이 우선 탐색이라는 것은 루트 노드에서 시작해서, 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법이다.

0, 1, 2, 3, 4

라는 노드가 있다고 가정했을때, 0부터 시작해서 갈수 있는 한 최대한 깊이 이동한다. (위의 예는 0,1,2,3,4 일 것이다)

만약 갈수 있는 최대한의 깊이로 이동해서 더이상 갈수 없다면, 바로 그 전의 노드로 이동한다 (3으로 백트래킹)

그 전의 노드로 돌아와서, 해당 노드의 다른 방향으로 더 깊이 갈수 있는 노드는 없는지 탐색한다.

또 없다면 다시 그 전의 노드로 백트래킹 (2번 노드로 회귀)해서 또 반복해서 탐색해준다.

보통 넓이를 우선적으로 탐색하는 BFS 보다 속도 자체는 느리지만, BFS보다 구현하기에 편리하므로 사용하는 경우가 많다. (재귀함수 또한 스택과 동일한 동작 원리를 가지기 때문이다.)

모든 노드를 방문 해주어야 하는 경우에 DFS를 사용한다.

자기 자신을 호출하는 재귀적 흐름의 형태를 띄고 있으며, stack 자료구조를 사용하여 구현한다.

- 전체적인 흐름도

1. 시작 노드를 스택에 넣고 방문 처리 한다.
2. 스택에 마지막으로 들어 온 노드에 방문하지 않은 인접 노드가 있는지 확인한다.

• 있다면, 방문하지 않은 인접 노드를 스택에 삽입해주고 방문 처리 한다.
• 없다면, 현재 노드 (스택에 마지막으로 들어온 노드)를 스택에서 추출(pop) 한다.

3. 2번 과정을 더이상 반복할수 없을때까지 반복한다.

- 사용 예시

1. BFS보다 더 짧은 코드로 구현해야 하는 경우

2. 큐 라이브러리를 사용할수 없는 경우\r

3. 트리에서 최단 거리 탐색을 구하는 경우

- 소스 코드 예시

위의 사진처럼 그래프가 이루어져있고, dfs 탐색을 한다고 가정해보자.

그래프 문제에서 정점과 간선이라는 용어가 등장하는데, 정점은 각 노드, 간선은 노드와 노드를 이어주는 선이라고 생각하면 된다.

let graph = [[], [2, 3, 4], [1], [1, 5, 6], [1, 7], [3, 8], [3], [4], [5]]; // 0번은 제외

let visited = Array(9).fill(false);

function dfs(graph, v, visited) {
  visited[v] = true; // 현재 노드를 방문 처리 해준다.

  console.log(v); // 현재 노드와 연결된 다른 노드를 재귀적으로 방문

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

dfs(graph, 1, visited);

문제 내에서 0번이 아니라 1번부터 탐색을 해야하는것이라면, 아예 0번 인덱스에 빈배열을 넣어줌으로써 간편성을 더할수 있다. (방문 처리 배열 또한 N+1으로 해준다.