[알고리즘] DFS

💡 DFS 알고리즘

• 완전 탐색 (모든 노드를 한 번씩 탐색하기 위한 방법)을 수행하기 위한 방법 중 하나로, 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식
• 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모 노드로 되돌아와서 (백트래킹), 부모 노드에 이전과는 다른 동작자를 적용하여 새로운 자식 노드를 생성
• DFS를 실제로 구현할 때는 스택 또는 재귀 함수를 이용
• → 재귀 함수는 내부적으로 스택과 동일한 동작 원리를 가지므로 구현의 편리성이 존재
• 완전 탐색을 목적으로 하는 경우, 탐색 속도가 BFS 보다 느린 경향이 있음
• 그럼에도 BFS 보다 구현하기 용이함
• DFS를 응용하여 모든 경우의 수를 계산하기 위한 백트래킹 알고리즘으로 사용 가능

 💡 자료구조

• 스택
• 먼저 들어온 데이터가 나중에 나가는 형식 (선입후출)의 자료 구조

• 그래프
• 2차원 배열로 그래프를 표현

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

 

💡 기본 동작 방식

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

 

💡 사용 예시

• 큐 라이브러리를 사용하지 못할 때
• 트리 순회, 점화식 구현 등 DFS (재귀 구조)에 특화된 문제인 경우
• 트리에서 최단 거리 탐색을 구하는 경우 (트리에서는 두 노드를 잇는 경로가 1개만 존재)

 

 💡 예제

let graph = [
    [],
    [2, 3, 4],
    [1],
    [1, 5, 6],
    [1, 7],
    [3, 8],
    [3],
    [4],
    [5]
];

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

function dfs(graph, v, visited) {
    visited[v] = true;
    console.log(v);
    for (let i of graph[v]) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(graph, i, visited);
        }
    }
}

dfs(graph, 1, visited);