깊이 우선 탐색 DFS

깊이 우선 탐색은 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다.

노드와 간선으로 이루어진 그래프에서 한 노드에서 시작해 더 이상 진행할 수 없을 때까지 깊게 들어가며 탐색하는 방식이다. 더 이상 진행할 수 없게 되면 마지막으로 방문했던 노드로 돌아가서 다른 경로를 탐색하는 백트래킹 기법을 사용한다.

 

DFS의 특징

1. 비선형 자료구조 탐색: DFS는 트리나 그래프와 같은 비선형 자료구조에서 사용되며, 모든 노드를 방문하기 위한 효과적인 방법을 제공
2. 스택 또는 재귀 이용: DFS는 내부적으로 스택을 사용하거나 재귀 호출을 통해 구현. 재귀 호출의 경우 시스템 스택이 사용
3. 경로 탐색 및 사이클 감지: DFS는 특정 경로의 존재 여부를 확인하거나 그래프 내 사이클을 감지하는 데 유용
4. 메모리 사용량: DFS는 탐색하는 동안 스택에 모든 방문 경로를 저장해야 하므로, 깊이가 매우 깊은 경우 상당한 메모리를 사용할 수 있다.
5. 솔루션 경로: 특히 퍼즐이나 미로 찾기 문제 같은 경우, DFS는 솔루션 경로를 찾는 데 사용될 수 있으나, 항상 최단 경로를 보장하지는 않는다.
6. 시간 복잡도: 그래프의 경우 DFS의 시간 복잡도는 O(V+E)입니다. 여기서 V는 정점의 수, E는 간선의 수이다.

 

DFS의 탐색 과정

1. 시작 노드 선택: DFS 탐색은 시작 노드를 선택하여 탐색을 시작. 시작 노드를 선택하고 방문하지 않은 노드를 찾아 방문을 시작
2. 현재 노드 방문 및 마킹: 시작 노드를 방문하고, 방문한 노드를 마킹하여 이미 방문한 노드임을 표시. 이렇게 마킹된 노드는 나중에 다시 방문하지 않도록 한다.
3. 인접 노드 확인: 현재 방문한 노드와 연결된 인접 노드들을 확인. 인접 노드 중에서 아직 방문하지 않은 노드를 선택한다. 이때, 인접 노드 중에서 어떤 순서로 선택할지에 따라 DFS의 다양한 변형이 가능하다.
4. 다음 노드 선택: 선택된 인접 노드 중에서 하나를 선택하여 다음에 탐색할 노드로 이동한. 선택된 노드를 현재 노드로 설정하고 방문한다.
5. 다음 노드로 이동: 선택된 노드로 이동하여 해당 노드를 현재 노드로 설정하고 다시 2단계로 돌아가서 현재 노드를 방문하고 마킹한다.
6. 더 이상 탐색할 노드가 없을 때까지 반복: 현재 노드에서 더 이상 방문하지 않은 인접 노드가 없을 때까지 위의 과정을 반복. 이때, 스택을 사용하여 현재 노드를 저장하거나, 재귀 호출을 통해 DFS를 구현할 수 있다.
7. 탐색 종료: 스택이 빈 상태가 되거나 모든 노드를 방문하고 마킹한 경우, DFS 탐색을 종료한다.

 

 

DFS 구현 방법

- 재귀적 방법

import java.util.*;

public class Graph {
    private LinkedList<Integer> adjLists[];
    private boolean visited[];

    // 그래프 생성자
    Graph(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList<Integer>();
    }

    // 간선 추가
    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    // DFS 구현
    void DFS(int vertex) {
        visited[vertex] = true;
        System.out.print(vertex + " ");

        Iterator<Integer> ite = adjLists[vertex].listIterator();
        while (ite.hasNext()) {
            int adj = ite.next();
            if (!visited[adj])
                DFS(adj);
        }
    }

    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, 3);

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

 

- 스택

import java.util.Stack;
import java.util.LinkedList;
import java.util.List;

class Graph {
    private int V; // 그래프의 노드 수
    private LinkedList<Integer>[] adjList; // 인접 리스트로 그래프 표현

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

    // 무방향 그래프의 간선 추가
    public void addEdge(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v);
    }

    // DFS 탐색
    public void DFS(int startNode) {
        boolean[] visited = new boolean[V]; // 방문 여부를 저장하는 배열
        Stack<Integer> stack = new Stack<>();

        visited[startNode] = true;
        stack.push(startNode);

        while (!stack.isEmpty()) {
            int currentNode = stack.pop();
            System.out.print(currentNode + " "); // 현재 노드를 출력

            for (int neighbor : adjList[currentNode]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(7); // 노드 개수를 맞게 설정
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        System.out.println("DFS 탐색 결과:");
        graph.DFS(0); // 시작 노드를 지정하여 DFS 실행
    }
}