알고리즘의 DFS(Depth-First Search): 그래프 탐색의 기본

 

안녕하세요! goodchuck 입니다!

블로그에 방문해주셔서 감사합니다!

 

 DFS의 개념

 

DFS(Depth-First Search)는 그래프를 탐색하는 알고리즘 중 하나로, 깊이를 우선하여 탐색하는 방법입니다. 이 알고리즘은 그래프의 한 노드에서 시작하여 깊이 방향으로 탐색하다가 더 이상 진행할 수 없는 상태에 이르면, 그 직전에 갈림길에서 다른 방향으로 다시 탐색을 진행합니다.

 

 DFS의 동작 원리

 

DFS는 다음과 같은 과정을 거쳐서 동작합니다:

1. 시작 노드를 방문하고, 이 노드를 방문한 것으로 표시합니다.

2. 현재 방문한 노드와 연결된 다른 노드 중 아직 방문하지 않은 노드가 있다면, 해당 노드로 이동하여 방문합니다.

3. 더 이상 방문하지 않은 노드가 없을 때까지 위 과정을 반복합니다.

 

 DFS의 장단점

 

**장점:**

- 구현이 간단하고 이해하기 쉬움

- 깊이 우선 탐색을 통해 해를 빠르게 찾을 수 있음

- 재귀적으로 구현될 때 자연스럽게 스택을 활용하므로 구현이 용이함

 

**단점:**

- 최단 경로를 보장하지 않음

- 무한 루프에 빠질 가능성이 있음

- 그래프가 매우 깊거나 무한히 깊은 경우에는 스택 오버플로우(Stack Overflow)가 발생할 수 있음

 

 DFS의 시간복잡도

 

DFS의 시간복잡도는 그래프의 크기에 비례합니다. 모든 노드와 간선을 방문하는 경우, 시간복잡도는 O(V+E)입니다. 여기서 V는 노드의 수이고, E는 간선의 수입니다.

 

 DFS의 사용처

 

DFS는 다양한 분야에서 활용됩니다:

- 그래프 탐색: 그래프에서 특정한 노드를 찾거나 연결된 모든 노드를 탐색할 때 DFS를 사용합니다.

- 재귀적 문제 해결: DFS는 재귀적으로 문제를 해결하는 데 사용될 수 있습니다. 예를 들어, 트리(Tree)의 깊이 우선 탐색은 DFS의 한 예입니다.

- 미로 찾기: DFS는 미로를 탐색하거나 경로를 찾는 데 사용될 수 있습니다.

 

 DFS의 재귀적 구현

 

재귀적으로 DFS를 구현할 수 있습니다. 재귀 함수를 사용하여 한 노드에서 다음 노드로 이동하고, 다시 그 노드에서 다음 노드로 이동하는 방식입니다.

 

// 그래프 정의

const graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F'],

    'D': ['B'],

    'E': ['B', 'F'],

    'F': ['C', 'E']

};



// 재귀적 DFS 함수 구현

function recursiveDfs(graph, node, visited = {}) {

    visited[node] = true;

    console.log(node);



    graph[node].forEach(neighbor => {

        if (!visited[neighbor]) {

            recursiveDfs(graph, neighbor, visited);

        }

    });

}



// 재귀적 DFS 실행

recursiveDfs(graph, 'A');

 

 DFS의 반복적 구현

 

또한, DFS는 반복적으로 구현할 수도 있습니다. 스택(Stack)을 사용하여 구현하며, 현재 노드와 연결된 다음 노드를 스택에 저장하고, 이후에 방문할 노드를 스택에서 꺼내어 탐색을 진행합니다.

 

// 반복적 DFS 함수 구현

function iterativeDfs(graph, start) {

    const visited = {};

    const stack = [start];



    while (stack.length) {

        const node = stack.pop();

        if (!visited[node]) {

            visited[node] = true;

            console.log(node);

            stack.push(...graph[node].filter(neighbor => !visited[neighbor]));

        }

    }

}



// 반복적 DFS 실행

iterativeDfs(graph, 'A');

 

DFS는 그래프 탐색에 있어서 매우 유용한 알고리즘으로, 깊이 우선으로 탐색하여 원하는 결과를 얻을 수 있습니다.

 

이상 글 읽어주셔서 감사합니다 다음에도 또 뵐수있길 빌겠습니다!