그래프 탐색 알고리즘, DFS(Depth-First Search)

 DFS(깊이 우선 탐색)

• 특정 방향으로 최대한 깊이 들어가서 빠져나오는 방식
• DFS는 스택 자료구조 사용

스택(Stack): 먼저 들어온 데이터가 나중에 나가는 형식 → FILO

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

인접 리스트 표현 방식

0
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	G
E	C, H
F	C
G	D
H	E

 

 

노드 방문 순서: A → B → C → E → H → F → D → G 

 

구현 특징

• 스택 혹은 재귀함수 이용
• 완전 탐색을 목적으로 하는 경우, 탐색 속도가 BFS보다 느림
• 구현의 편리성 때문에 BFS 대신 DFS를 사용하는 경우가 많음

사용 예시

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

DFS 소스 코드 예시

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

function dfs(graph, v, visited) {
    visited[v] = true; // 현재 노드 방문 처리
    console.log(v);
    // 현재 노드와 연관된 다른 노드를 재귀적으로 방문
    for (const i of graph[v]) {
        if (!visited[i]) {
            dfs(graph, i, visited);
        }
    }
}

// 각 노드가 연결된 정보를 표현
const graph = [
    [], // 편의성을 위해 0번 노드 사용하지 않음
    [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);