[알고리즘/DFS] 깊이 우선 탐색(Depth First Search)

깊이 우선 탐색(DFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

• 미로를 탐색할 때 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가까운 갈림길로 돌아와 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 그래프에서 모든 노드를 방문하고자 할 때 더 선호되는 편이다.
• 전위 순회를 포함한 다른 형태의 트리 순회는 모두 깊이 우선 탐색의 한 종류이다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.(안하면 무한 루프에 빠질 위험 있음)
• 깊이 우선 탐색은 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 가지고 있다.

---

   A		//시작 노드
  / \
 B   C		//A와 연결된 노드
 |   |
 D   E		//각 B, C와 연결된 노드

우선 위의 그래프를 스텍을 이용해 DFS를 구현해 보자

Stack: [A]
Visited: []

시작 노드 A를 스택에 넣고 방문한다.

스택에서 노드를 하나 꺼내고, 해당 노드와 연결된 방문하지 않은 노드를 스택에 넣는다.

이때, 가능한 깊이 들어가서 탐색한다.

Stack: [B, C]
Visited: [A]

B를 꺼내 방문한다. B와 연결된 노드 D가 들어간다.

Stack: [D, C]
Visited: [A, B]

D를 꺼내 방문한다.

D는 더 이상 연결된 노드가 없으므로 스택에서 C가 꺼내진다.

C와 연결된 노드 E가 스택에 들어간다.

Stack: [E]
Visited: [A, B, D, C]

마지막으로 E를 꺼내 방문한다.

스택에서 노드가 모두 꺼내지면서 DFS 탐색이 완료된다.

---

깊이 우선 탐색의 구현

//스택을 이용
import java.util.*;

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);
    }

    // DFS 시작
    void DFS(int start) {
        boolean visited[] = new boolean[V];	//방문했으면 true
        Stack<Integer> stack = new Stack<>();

        stack.push(start); // 시작 노드를 스택에 넣음

        while (!stack.isEmpty()) {
            int current = stack.pop();

            if (!visited[current]) {
                visited[current] = true;
                System.out.print(current + " ");

                for (Integer neighbor : adjList[current]) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("DFS starting from vertex 0:");
        graph.DFS(0);
    }
}

---

//재귀 함수를 이용
import java.util.*;

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);
    }

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

        for (Integer neighbor : adjList[v]) {
            if (!visited[neighbor]) {
                DFS(neighbor, visited);
            }
        }
    }

    // DFS 시작
    void DFS(int start) {
        boolean visited[] = new boolean[V];
        DFS(start, visited);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("DFS starting from vertex 0:");
        graph.DFS(0);
    }
}