DFS [깊이 우선 탐색] 란?

그래프 탐색

그래프 탐색 알고리즘 중 대표적으로 사용되는 DFS에 대해 알아보자.
그래프 탐색이란 그래프 내 임의의 한 정점에서 시작해서 모든 정점들을 탐색하는 것을 말한다.
DFS는 현재 정점에서 갈 수 있는 정점까지 들어가면서 탐색하는 것이고, 또 다른 대표적인 그래프 탐색 기법인 BFS는 현재 정점에 연결되어 있는 가까운 정점들부터 차례대로 탐색한다.

DFS (Depth-First Search)

DFS는 깊이 우선 탐색 이라고도 부르는 방법으로 선택한 정점에서 가장 깊게 들어갈 수 있는 부분까지 들어가며 탐색하는 방법이다.

• DFS 구현 방법
  • 스택
  • 재귀함수
• DFS의 장점과 단점
  • 장점
    • 현 경로상의 노드들만을 기억하므로 저장공간을 적게 사용한다.
    • 목표노드가 깊은 단계에 있는 경우 해를 빠르게 구할 수 있다.
  • 단점
    • 해가 없는 경로에 깊이 빠질 가능성이 있으므로 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
    • 목표에 이르는 경로가 다수일 경우, DFS는 해에 다다르면 탐색을 끝내버리기 때문에 이 때 얻어진 해는 최단, 최적 경로가 아닐 수 있다.

재귀를 이용한 DFS 구현

C++

bool visited[101] = {};

void dfs(vector<int> graph[], int x) {
    visited[x] = true;
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!visited[y]) dfs(graph, y);
    }
}

JAVA

public static void dfs(int v){
        // 현재 노드 방문 처리
        visited[v] = true;
        // 방문 노드 출력
        System.out.print(v + "");
        
        // 인접 노드 탐색
        for (int i : graph[v]){
            // 방문하지 않은 인접 노드 중 가장 작은 노드를 스택에 넣기
            if (visited[i]==false){
                dfs(i);
            }
        }
    }

스택을 이용한 DFS 구현

C++

bool visited[101] = {};
void dfs_stack(vector<int> graph[], int x) {
    stack<int> s;
    s.push(x);
    visited[x] = true;

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        for (int i = 0; i < graph[node].size(); i++) {
            int nextNode = graph[node][i];

            if (!visited[nextNode]) {
                visited[nextNode] = true;\
                s.push(node);
                s.push(nextNode);
                break;
            }
        }
    }
}

JAVA

void dfs(int [][]graph,int start, boolean [] visited){
        //시작 노드를 방문 처리
        visited[start] = true;
        System.out.print(start + " ");//방문 노드 출력
        
        Deque<Integer> stack = new LinkedList<>();
            stack.push(start); //시작 노드를 스택에 입력
            
            while(!stack.isEmpty()){
                int now = stack.peek();
                
                boolean hasNearNode = false; // 방문하지 않은 인접 노드가 있는지 확인
                //인접한 노드를 방문하지 않았을 경우 스택에 넣고 방문처리
                for(int i: graph[now]){
                    if (!visited[i]) {
                        hasNearNode = true;
                        stack.push(i);
                        visited[i] = true;
                        System.out.print(i + " ");//방문 노드 출력
                        break;
                    }
                }
                //반문하지 않은 인접 노드가 없는 경우 해당 노드 꺼내기
                if(hasNearNode==false)
                    stack.pop();
            }