DFS (Depth First Search)

DFS (Depth First Search) 설명:

DFS는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 노드에서 시작하여 가장 깊은 부분까지 탐색한 다음 다시 돌아와 다음 경로를 탐색하는 방식입니다. DFS는 스택을 사용하여 구현할 수 있으며, 재귀적 방식으로도 자주 구현됩니다.

DFS의 기본 원칙:
1. 시작 노드를 스택에 넣는다.
2. 현재 스택의 맨 위 노드를 확인한다.
3. 해당 노드에 연결된 아직 방문하지 않은 노드가 있다면 그 노드를 스택에 넣고 방문한다. 연결된 노드가 없거나 모두 방문했다면 스택에서 그 노드를 꺼낸다.
4. 스택이 비어있을 때까지 2-3단계를 반복한다.

JavaScript에서의 DFS 예제 (재귀를 사용한 방식):

let visited = {};  // 방문한 노드를 기록
let graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
};

function dfs(node) {
    if (node in visited) return;  // 이미 방문한 노드는 재방문하지 않음

    visited[node] = true;
    console.log(node);  // 현재 노드 출력

    graph[node].forEach(neighbor => {
        dfs(neighbor);  // 연결된 모든 노드에 대해 DFS 실행
    });
}

dfs('A');  // A부터 시작하는 DFS

DFS의 사용 사례:
1. 싸이클 탐지: 그래프 내에서 순환구조(싸이클)가 있는지 확인할 때 사용합니다.
2. 경로 탐색: 두 노드 사이에 경로가 존재하는지 확인하거나 해당 경로를 찾을 때 사용합니다.
3. 연결 요소(Connected Components) 탐색: 그래프 내의 모든 연결 요소를 찾을 때 사용합니다.
4. 퍼즐 및 게임의 해답 찾기: 예를 들어, 미로 찾기나 8-puzzle과 같은 문제에서 해답을 찾기 위해 DFS를 사용할 수 있습니다.

장점:
1. 모든 노드를 방문하는 것을 보장합니다.
2. 현재 경로에 대한 정보를 유지하기 쉽습니다 (스택을 사용하기 때문).

단점:
1. 모든 가능한 경로를 탐색하기 때문에 시간이 오래 걸릴 수 있습니다.
2. BFS (Breadth First Search)에 비해 최단 경로를 찾는 데에는 적합하지 않을 수 있습니다.

DFS는 특히 문제를 단순화하고 모든 가능한 경로를 탐색해야 할 때 유용합니다. 하지만 최적의 해답이나 최단 경로를 찾기 위해선 다른 알고리즘 또는 방법이 필요할 수 있습니다.