깊이 우선 탐색(DFS)

한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 알고리즘.

주로 스택 혹은 재귀함수를 사용합니다.

특징

• 메모리 사용이 적음
• 목표 노드가 깊은 단계에 있을 때 유리
• 모든 노드를 방문하고자 할 때 적합합니다.

사용 사례

• 미로 찾기
• 위상 정렬
• 사이클 탐지

예시 코드

import java.util.*;

class Graph {
    private int V; // 노드의 수
    private LinkedList<Integer>[] adj; // 인접 리스트

    // 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // DFS를 위한 재귀 함수
    void DFSUtil(int v, boolean visited[]) {
        // 현재 노드를 방문한 것으로 표시하고 출력
        visited[v] = true;
        System.out.print(v + " ");

        // 방문한 노드와 인접한 모든 노드를 가져온다
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // 주어진 노드를 시작 노드로 DFS 탐색
    void DFS(int v) {
        // 노드의 방문 여부 판단 (초깃값: false)
        boolean visited[] = new boolean[V];

        // v를 시작 노드로 DFSUtil 재귀 호출
        DFSUtil(v, visited);
    }

    // 메인 메서드
    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("주어진 정점 2에서 시작한 깊이 우선 탐색");

        g.DFS(2);
    }
}

각 부분 설명

1. Graph 클래스
   • 그래프를 표현하며, 노드의 수(V)와 인접 리스트(adj)를 가집니다.
   • addEdge 메소드로 그래프에 간선을 추가할 수 있습니다.
2. DFSUtil 메소드
   • DFS 알고리즘을 구현한 재귀 메소드입니다.
   • 현재 노드를 방문 처리하고, 인접한 노드들을 확인합니다.
   • 방문하지 않은 인접 노드가 있으면, 그 노드에 대해 재귀적으로 DFSUtil을 호출합니다.
3. DFS 메소드
   • DFS 탐색을 시작하는 메소드입니다.
   • 방문 여부를 체크할 배열을 초기화하고, DFSUtil을 호출합니다.

동작 방식

1. 시작 노드를 방문 처리
2. 시작 노드의 인접 노드중 방문하지 않은 노드를 선택
3. 선택한 노드에 대해 재귀적으로 1-2과정을 반복
4. 더 이상 방문할 인접 노드가 없으면 이전 노드로 돌아감
5. 모든 노드를 방문할 때까지 2-4 과정을 반복

시간 복잡도는 O(V + E)이다. V는 노드의 수, E는 간선의 수이다.