[JAVA/알고리즘] 깊이 우선 탐색 (DFS) 이란? / 자바 사용 예시 총 정리

탐색

: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 

 

어떤 메모리 구조를 가졌느냐에 따라 효율적인 탐색 방법이 갈리긴 하지만,

일반적으로 탐색에 쓰이는 알고리즘 중 대표적인 DFS에 대해 알아보도록 하겠다.

 

 

깊이 우선 탐색(DFS)은 

이진 트리 구조를 기반의 효율적인 탐색 방법 중 하나이다.

Depth First Search

= 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 

 

 

▷ 깊이 우선 탐색(DFS) 의 특징

-다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식이다.
-스택 메모리 구조에 기초하여 구현이 간단하다. 
-검색 대상 그래프가 크거나 경로의 특징을 저장해둬야 하는 문제에 유리

 

리프 노드(시작 정점)부터 시작해 정점과 연결 된 모든 정점들을 먼저 순회한 후,

되돌아와 탐색하지 않은 정점을 시작점으로 잡아 연결 된 정점을 모두 순회한다.

가지를 타고 가는 것을 생각해보면 쉽다.

출처 - https://en.wikipedia.org/wiki/Depth-first_search

 

 

깊이 우선 탐색의 순회 순서를 직관적으로 나타내면 위와 같다.

참고로

꼭 방향이 있는 이진 트리가 아니어도,

방향이 없는 그래프에서도 해당 알고리즘을 사용한 순회가 가능하다.

 

 

 

 

 

▷ 깊이 우선 탐색(DFS) 알고리즘 구현 (JAVA)

이걸 JAVA 코드로 구현하는 방법은 두 가지가 있는데

 

1) 스택으로 구현하는 방법

2) 재귀 함수로 구현하는 방법

 

둘의 성능 차이는 크게 없다.

가독성의 차이는 있으나, 상황에 맞게 적용하는 것이 베스트.

 

 

 

 

1) DFS 스택으로 구현하는 방법

public static String dfs(int v, boolean node[][]) {
    StringBuilder sb = new StringBuilder();
    Stack<Integer> stack = new Stack<>();
    boolean visited[] = new boolean[n+1];
    stack.add(v);
    int idx;
    while(!stack.isEmpty()) {
        idx = stack.pop();
        if(visited[idx])
            continue;
        visited[idx] = true;
        sb.append(idx+" ");
        for(int i=0; i<n; i++)
            if(node[idx][i] && !visited[i])
                stack.add(i);
    }
    return sb.toString();
}

 

 

 

 

스택 자료구조는 다음 글을 참고하자.

[JAVA/자료구조] 자바 Stack 사용법 / 스택 예시 총 정리 - 문자열 뒤집기, 괄호 짝 맞추기

 

 

 

 

 

 

 

 

2) DFS 재귀함수로 구현하는 방법

public static void dfs(int x) {
        visited[x] = true; 
        sb.append(x).append("\n");
        for (int i = 0; i < graph[x].length; i++) {
            if (!visited[graph[x][i]]){
                dfs(graph[x][i]);
            }
        }
    }

위의 예시는 2차원 배열을 사용했지만 

이중 연결 리스트 등을 사용하는 방법도 있다.

 

 

 

개인적으로 2차원 배열은 메모리 초과의 우려가 있긴 하다....

2차원 배열 대신,

 

HashMap<Integer,ArrayList<Integer>>

Queue<Integer>

ArrayList<ArrayList<Integer>>

PriorityQueue<Integer>

 

등을 활용해 구현하는 것이 좀 더 효율성의 측면에서 우수할 것이다.

 

 

 

자바 연결리스트 구현 방법은 다음 글을 참고하자.

[JAVA/자료구조] 자바 연결리스트 사용법 (Linked List) 구현 / 예제 정리

 

 

 

 

 

 

 

▷ 깊이 우선 탐색(DFS) 알고리즘 사용 예시

 

대표적인 DFS 알고리즘 사용 예시는 다음과 같다.

 - 전위 순회(preorder traverse) 
 - 미로 탐색
 - 그래프 사이클 찾기
 - 그래프 연결 요소 찾기

등...

 

 

 

 

번외로,

DFS 탐색에서 재귀 함수를 이용할 때 참고하면 좋을 블로그 글을 함께 첨부하겠다.

반복과 재귀 : DFS 문제를 재귀로 구현하면 편리한 이유