TIL-2024.03.09 - DFS - 깊이 우선 탐색

 

 

 

------- DFS

 

설명:

• DFS는 깊이 우선으로 그래프를 탐색하는 알고리즘.
• 이 알고리즘은 한 경로를 따라 최대한 깊이 탐색한 후, 다른 경로로 이동하여 탐색을 계속 진행.
• DFS는 스택(stack) 또는 재귀 함수를 사용하여 구현.

 

동작 원리:

• 시작 노드를 스택에 넣고 방문 표시.
• 스택이 빌 때까지 다음을 반복:
  • 스택에서 하나의 노드를 빼기.
  • 해당 노드와 인접한 미방문 노드 중 하나를 선택하여 스택에 넣고 방문 표시.
  • 더 이상 진행할 수 없을 때까지 재귀적으로 반복.
• 모든 노드가 방문될 때까지 반복.

 

 

특징:

• 깊이 우선 탐색은 해를 찾을 때까지 모든 경로를 탐색.
• 메모리를 적게 사용.
• 재귀 함수 또는 스택을 사용하므로 구현이 다소 복잡.

 

 

예제: 

 

function dfs(graph, start, visited = new Set()) {
    if (!visited.has(start)) {
        visited.add(start);
        console.log(start);

        let neighbors = graph[start];
        for (let neighbor of neighbors) {
            dfs(graph, neighbor, visited);
        }
    }
}

// 예제 그래프
let graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E', 'F'],
    'D': [],
    'E': [],
    'F': []
};

console.log("DFS 결과:");
dfs(graph, 'A');

 

 

 

BFS와의 차이:

 

그래프:
    A
   / \
  B   C
 /   / \
D   E   F

BFS 결과: A -> B -> C -> D -> E -> F
DFS 결과: A -> B -> D -> C -> E -> F



예시:
1. 미로 문제: DFS가 미로를 탐색하는 데 유용합니다. 
> 깊이 우선 탐색은 한 방향으로 끝까지 탐색하고 막힌 경우 이전 단계로 돌아가서 다른 경로를 탐색합니다.

2. 최단 경로 문제: BFS가 최단 경로를 찾는 데 유용합니다. 
> 너비 우선 탐색은 모든 인접한 노드를 우선 탐색하므로 최단 경로를 먼저 찾을 수 있습니다.

 

 

사용 이유:

1. 깊이 우선 탐색: 그래프의 깊은 부분을 탐색할 때 유용합니다. 예를 들어, 미로 찾기, 그래프의 모든 경로 찾기 등에서 사용.
2. 그래프 순회: DFS는 그래프를 순회하고 모든 노드를 탐색하는 데 유용.
3. 사이클 탐색: DFS는 사이클을 탐색하고 찾는 데 사용. 한 번 방문한 노드를 다시 방문하면 사이클이 있음을 표현.