깊이 우선 탐색 ( DFS )

깊이 우선 탐색(DFS, Depth-First Search)은 그래프를 탐색하는 알고리즘 중 하나로, 한 경로를 따라 최대한 깊이까지 탐색한 후, 다음 경로로 이동하는 방식이다. DFS는 스택(Stack)이나 재귀(Recursion)를 사용하여 구현할 수 있다. 주로 그래프의 탐색, 경로 찾기, 연결 요소 확인 등에 활용된다.

 

DFS의 작동 방식

1. 출발 노드 선택: 시작 노드를 선택하고, 해당 노드를 방문한 것으로 표시한다.
2. 인접한 미방문 노드 탐색: 선택한 노드의 인접한 미방문 노드 중 하나를 선택한다.
3. 선택한 노드로 이동: 선택한 노드로 이동하여 그 노드를 방문한 것으로 표시한다.
4. 이동한 노드의 인접 미방문 노드 탐색: 이동한 노드의 인접한 미방문 노드 중 하나를 선택하여 이동한다.
5. 반복: 이동한 노드의 인접 미방문 노드가 더 이상 없을 때까지 위의 단계를 반복한다.
6. 백트래킹: 더 이상 갈 곳이 없으면 이전 단계로 돌아가서 다른 경로를 탐색한다.
7. 모든 노드 방문 완료 시 종료: 모든 노드를 방문하거나 원하는 조건을 만족하면 탐색을 종료한다.

 

DFS의 특징

• 깊이 우선 탐색은 가능한 깊이까지 탐색하므로, 재귀 구조나 스택을 사용할 때 최대 재귀 깊이에 주의해야한다.
• 그래프의 연결 요소를 확인하거나, 경로의 존재 여부 등을 판단하는 데 유용하다. 미로 찾기와 같은 경로 탐색 문제에도 DFS를 활용할 수 있다.

 

DFS의 구현 방법 (Java 예시 - 재귀)

class Graph {
    private int V;
    private LinkedList<Integer> adjList[];

    Graph(int v) {
        V = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjList[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adjList[v].add(w);
    }

    void DFS(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adjList[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFS(n, visited);
        }
    }

    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFS(v, visited);
    }
}

public class DFSTest {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Depth First Traversal (starting from vertex 2): ");
        g.DFS(2);
    }
}

 

DFS를 이해는데 헷갈릴 수 있는 부분

• 재귀 호출과 스택
  DFS는 보통 재귀 호출이나 스택을 사용하여 구현된다. 이때, 재귀 호출은 내부적으로 스택의 원리를 따른다. 따라서 스택이 어떻게 동작하는지 이해하지 않으면 재귀 구현이 이해하기 어려울 수 있다.
• 백트래킹과 재방문
  DFS에서 백트래킹은 더 이상 탐색할 경로가 없을 때, 이전 단계로 돌아가는 것을 의미한다. 그러나 모든 경로를 탐색한 후에도 백트래킹을 할 수 있다. 이때 중요한 것은 이미 방문한 노드를 다시 방문하는 것이 문제 없다는 점이다. 그렇기 때문에 방문 여부를 기록하고 관리하는 것이 중요하다.
• 최단 경로를 찾는 것이 아닐 수 있음
  DFS는 맨 처음 발견한 경로를 따라 끝까지 탐색한 후, 다음 경로로 넘어간다. 이러한 특성 때문에 최단 경로를 보장하지 않는다. 최단 경로를 찾아야 하는 경우 BFS(Breadth-First Search)가 더 적합한 선택일 수 있다.
• 스택 오버플로우
  DFS는 깊이 우선 탐색이므로 재귀 호출의 깊이가 깊어질 수 있다. 따라서 스택 오버플로우가 발생할 수 있다. 이를 방지하기 위해 재귀의 깊이를 제한하거나 반복적인 방법으로 구현하는 등의 대책이 필요할 수 있다.
• 방향 그래프와 무방향 그래프
  DFS는 방향 그래프와 무방향 그래프에서 모두 사용될 수 있다. 방향 그래프에서는 간선의 방향을 고려하여 탐색해야 한다.
• 순환 그래프와 비순환 그래프
  순환 그래프에서는 어떤 경로를 따라도 무한히 탐색할 수 있다. 따라서 순환 그래프의 경우 DFS는 반드시 어느 정도의 종료 조건이 필요하다.
• 방문 순서의 영향
  DFS는 어떤 순서로 노드를 방문하느냐에 따라 결과가 달라질 수 있다. 따라서 그래프의 구조와 문제의 요구사항에 따라 방문 순서를 결정하는 것이 중요하다.