깊이 우선 탐색 (DFS : Depth First Search) - JAVA

깊이 우선 탐색(DFS : Depth First Search)

---

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나입니다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 입니다. 구현은 재귀 함수, 스택을 이용하며 시간 복잡도는 O(V + E) V = 노드 수, E = 엣지 수 입니다. 

 

출처 : https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

 

장단점

• 장점
  • 현 경로상의 노드들만 기억하면 되기때문에 저장 공간의 수요가 적음
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있음
  • 얻어진 해가 최단 경로가 된다는 보장이 없음

 

구현 방법

---

DFS를 사용하기 위해서는 먼저 그래프를 구현 해야합니다. 그래프를 구현하는 방법은 인접 행렬과 인접 리스트 2가지의 방법이 있습니다. 이에 대한 정보는 아래의 주소에서 확인 할 수 있습니다.

인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List) - JAVA

 

DFS를 구현 하는 방법은 재귀(Recursive)를 이용하는 방법과 스택(stack)을 이용하는 방법이 있습니다. 먼저 재귀를 이용한 방법입니다.

 

재귀(Recursive)

static ArrayList<ArrayList<Integer>> graph;
static boolean[] visited;
// visited 배열과 graph 는 전역 변수로 선언을 해주어야 함

public static void dfs(int cur) {
    visited[cur] = true;
    for(int i = 0; i < graph.get(cur).size(); i++) {
    	// 다음 노드가 방문 하지 않았다면 방문
        if(!visited[graph.get(cur).get(i)]) {
            dfs(graph.get(cur).get(i));
        }
    }
}

그래프가 모두 연결되어 사이클(Cycle)을 형성하게 되면 이미 방문한 노드를 계속해서 방문하게 되어 무한 루프를 돌게되는 경우를 주의 해야합니다. 때문에 boolean 형태의 visited 배열을 두어 방문의 유무를 체크하며 방문하여 문제를 해결 하면 되겠습니다.

 

스택(Stack)

// 중복 방문을 막기위해 체크 해주어야 함 방문을 했으면 true
boolean[] visited = new boolean[N+1];
Stack<Integer> stack = new Stack<>();

// 1번 부터 N번까지의 노드가 있다고 가정
for(int i = 1; i <= N; i++) {
    if(!visited[i]) {
    	// 스택에 방문하지 않은 노드를 입력
        stack.push(i);
        // 스택이 비어있게되면 탐색이 완료된 것
        while(!stack.isEmpty()) {
            int cur = stack.pop();
            if(!visited[cur]) {
            	// 현재 노드 방문 체크
                visited[cur] = true;
                // 현재 노드와 연결된 노드를 스택에 push
                for(int j = 0; j < graph.get(cur).size(); j++) {
                    stack.push(graph.get(cur).get(j));
                }
            }
        }
    }
}