DFS(깊이 우선 탐색) 이해하기

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

DFS를 활용한 완전 탐색

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

DFS 기본 동작 방식

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

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

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

DFS 구현 특징

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

DFS 사용 예시

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

DFS 소스 코드 예시

// DFS 메서드 정의
function dfs(graph, v, visited) {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);
  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (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]];
// 각 노드가 방문된 정보를 표현
const visited = Array(9).fill(false);
// 정의된 DFS 함수 호출
dfs(graph, 1, visited);

24479 01 Data Structure