DFS(Depth-First Search) 알고리즘

깊이 우선 탐색 알고리즘

그래프 탐색 알고리즘: DFS, BFS

탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

• DFS는 스택 자료구조 사용
• DFS는 2차원 배열(리스트)로 그래프 표현
• 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법
  → 완전탐색 수행하기 위해 사용할 수 있는 가장 간단한 방법 중 하나

❗️인접 리스트 표현 방식

노드	인접한 노드들
1	2, 3
2	1, 5
3	1, 4, 5
4	3, 5
5	2, 3, 4

기본 동작 방식

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

→ 각 노드 및 간선에 대하여 한 번씩만 확인가능!

노드	인접한 노드들
A	B, C, D
B	A
C	A, E, F
D	A, G
E	C, H
F	C
G	D
H	E

노드 방문 순서: A → B → C → E → H → F → D → G
✓ 특정 방향으로 최대한 깊에 들어가서 빠져나오는 방식

구현 특징

• 스택 혹은 재귀 함수 이용
  → 재귀 함수는 내부적으로 스택과 동일한 동작 원리를 가지므로, 구현의 편리성 존재
• 완전탐색을 목적으로 하는 경우, 탐색속도가 BFS보다 느림
• 구현의 편리성 떄문에 BFS 대신 DFS를 사용하는 경우가 많음

사용 예시

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

⭐️ DFS JS 코드 예시 ⭐️

// DFS 메서드 정의
function dfs(graph, v, visited){
  // 현재 노드를 방문 처리
  visited[v] = ture;
  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for(let i of graph[v]){
    if(!visited[i]){
      dfs(graph, i, visited);
    }
  }
}

// 각 노드가 연결된 정보를 표현
graph = [
  [], // 편의성을 위해 0번 노드 사용하지 않음
  [2, 3, 4],
  [1],
  [1, 5, 6],
  [1, 7],
  [3, 8],
  [3],
  [4],
  [5]
];

// 각 노드가 방문된 정보를 표현
vistied = Array(9).fill(false);

// 정의된 DFS 함수 호출
dfs(graph, 1, visited);

→ 도달 가능한 끝 위치까지 도달했다면, 다시 최근의 "갈림길"로 돌아가서, 다른 위치로도 가보는 방식과 유사