javascript - DFS(Depth-First Search)

DFS(Depth-First Search)

그래프 탐색을 위한 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다. DFS는 그래프의 모든 노드를 방문하고, 각 노드를 한 번씩만 방문하며 연결된 모든 노드를 탐색합니다.

DFS의 작동 방식은 다음과 같습니다:

시작 노드를 방문하고, 방문한 노드를 "방문한 노드" 목록에 추가합니다.
현재 노드와 연결된 이웃 노드들을 확인합니다.
이웃 노드들 중 방문하지 않은 노드가 있으면, 그 이웃 노드로 이동하여 재귀적으로 탐색합니다.
모든 이웃 노드를 방문했거나 더 이상 방문할 이웃 노드가 없으면, 이전 단계로 돌아가서 탐색을 계속합니다.
DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다. 스택을 사용하는 경우, 방문한 노드들을 스택에 차례로 쌓고, 더 이상 방문할 이웃 노드가 없을 때 스택에서 최근에 추가된 노드를 꺼내어 탐색을 계속합니다. 재귀 함수를 사용하는 경우에는 재귀 호출을 통해 DFS를 구현합니다.

DFS는 그래프의 깊은 부분을 우선적으로 탐색하기 때문에, 깊은 경로를 찾거나 그래프의 구조를 파악하는 데에 적합합니다. 하지만 최단 경로를 찾는 문제에는 적합하지 않을 수 있습니다.

DFS를 활용하여 그래프를 탐색하는 과정을 설명해보겠습니다. 다음은 인접 리스트 형태의 그래프를 기준으로 DFS를 적용하는 예시입니다

const graph = {
  1: [2, 3],
  2: [4],
  3: [5],
  4: [],
  5: []
};

const visited = {};

function dfs(node) {
  if (!node) return;

  visited[node] = true;
  console.log('방문한 노드:', node);

  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor);
    }
  }
}

dfs(1);

이 예제에서는 시작 노드를 1로 설정하고, DFS를 실행합니다. 방문한 노드들은 visited 객체를 통해 기록하며, 각 노드를 방문할 때마다 해당 노드 번호를 출력합니다. DFS를 통해 그래프의 모든 노드를 방문하게 됩니다.

DFS를 구현하는 방식은 언어에 따라 조금씩 달라질 수 있으며, 스택이나 재귀 함수의 사용 유무에 따라서도 구현 방법이 달라질 수 있습니다. 하지만 DFS의 기본 원리는 그래프의 구조를 깊이 우선으로 탐색하는 것이므로, 이를 기준으로 코드를 작성하면 됩니다.