[그래프] 깊이 우선 탐색 DFS

DFS

DFS는 그래프나 트리에서 탐색하는 알고리즘 중 하나로, 시작점에서부터 가능한 깊은 곳까지 탐색한 후에 백트래킹(backtracking)하여 다른 경로를 탐색하는 방식입니다. 즉, 한 경로를 따라 최대한 깊게 탐색한 후, 더 이상 탐색할 노드가 없으면 이전 노드로 돌아가 다른 경로를 탐색합니다.

특징

1. 깊이 우선 탐색: DFS는 가능한 한 깊은 노드까지 탐색한 후, 더 이상 내려갈 수 없을 때 돌아가서 다른 경로를 탐색합니다. 노드를 "깊이"를 기준으로 탐색합니다.
2. 스택(Stack)을 이용한 구현: DFS는 노드를 저장하고 탐색 순서를 관리하기 위해 스택 자료 구조를 사용합니다. 현재 노드에서 인접한 노드를 스택에 추가하고, 가장 나중에 추가된 노드부터 처리합니다(LIFO, Last In, First Out 방식).
3. 백트래킹: 깊이 우선 탐색은 탐색 도중 더 이상 진행할 수 없는 경우, 이전의 상태로 돌아가 다른 경로를 탐색합니다. 이 과정을 백트래킹이라고 합니다.
4. 재귀적 구현: DFS는 재귀적으로 구현될 수 있습니다. 노드를 탐색할 때, 인접 노드를 재귀 호출하여 탐색합니다.

장단점

• 장점:
  • 공간 복잡도가 BFS보다 낮을 수 있습니다. DFS는 스택(혹은 재귀 호출)을 사용하므로 큐에 비해 더 적은 공간을 필요로 할 수 있습니다.
  • 경로가 매우 깊은 경우에도 유용합니다.
• 단점:
  • 최단 경로를 보장하지 않습니다. 깊이 우선 탐색은 최단 경로를 찾는 데 적합하지 않습니다.
  • 사이클이 있는 그래프에서 무한 루프에 빠질 수 있으며, 이를 방지하기 위해 방문한 노드를 추적해야 합니다.

시간 및 공간 복잡도

• 시간 복잡도: O(V+E)O(V + E)O(V+E) (V는 정점의 수, E는 간선의 수)
  • 각 노드를 한 번씩 방문하고, 각 간선을 한 번씩 처리하기 때문입니다.
• 공간 복잡도: O(V)O(V)O(V)
  • 스택 또는 재귀 호출에 의해 모든 노드를 저장할 필요가 있습니다.

의사 코드 + Java 코드

DFS(graph, startNode):
    1. 스택(Stack) 생성
    2. 방문 여부를 기록할 리스트 또는 배열 생성
    3. 시작 노드를 스택에 추가하고 방문 처리
    4. 스택이 빌 때까지 다음을 반복:
        a. 스택에서 노드를 하나 꺼냄
        b. 해당 노드의 모든 인접 노드를 확인
        c. 방문하지 않은 인접 노드를 스택에 추가하고 방문 처리

import java.util.*;

public class GraphTraversal {

    private Map<Integer, List<Integer>> graph;

    public GraphTraversal(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
    }

    public void dfs(int startNode) {
        // 방문한 노드를 기록하기 위한 집합
        Set<Integer> visited = new HashSet<>();
        // DFS에 사용할 스택
        Stack<Integer> stack = new Stack<>();

        // 시작 노드를 스택에 넣고 방문 표시
        stack.push(startNode);
        visited.add(startNode);

        while (!stack.isEmpty()) {
            // 스택에서 노드를 꺼내서 처리
            int currentNode = stack.pop();
            System.out.println("Visited node: " + currentNode);

            // 현재 노드의 이웃들을 확인
            List<Integer> neighbors = graph.getOrDefault(currentNode, new ArrayList<>());
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
}

 

DFS의 활용 예시

• 경로 찾기: 특정 노드에서 다른 노드로 가는 경로를 찾을 때 유용합니다.
• 연결성 검사: 그래프가 연결되어 있는지 확인하는 데 사용합니다.
• 그래프의 사이클 탐지: 사이클이 있는지 확인하는 데 사용할 수 있습니다.
• 토폴로지 정렬: 방향 그래프에서 정렬을 수행할 때 DFS를 사용할 수 있습니다.