탐색 알고리즘 DFS

DFS(Depth-First Search)

깊이우선탐색이라고도 불린다. 그래프를 넓게 탐색하기 보다는, 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS의 구체적인 동작과정은 다음과 같다.

• 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 위 과정을 더이상 수행할 수 없을 때까지 반복한다.

*'방문처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는것을 의미. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.

DFS는 스택 자료구조에 기초하며, 탐색을 수행함에 있어서 시간복잡도가 O(N)이 소요된다. 스택을 이용해서 DFS를 구현할 수 있지만, 재귀함수를 사용하면 코드를 더 간결하게 사용할 수 있다.

스택을 이용한 DFS (java)

package DFS_BFS;

import java.util.Stack;

public class StackDFS {

    // 방문처리 배열
    static boolean[] visited = new boolean[9];
    // 그래프의 연결상태를 2차원 배열로 표현
    // 인덱스가 각각의 노드번호가 되고 0번 인덱스는 아무것도 없는 상태
    static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};

    //DFS 사용할 스택
    static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) {
        // 시작노드 1을 스택에 넣어주고 방문처리 해줌
        stack.push(1);
        visited[1] = true;

        // 스택에 더이상 값이 없을때까지 반복
        while(!stack.isEmpty()) {
            //스택에서 값 꺼냄
            int nodeIndex = stack.pop();
            System.out.println(nodeIndex + " -> ");
            //꺼낸 노드와 인접한 노드 순회
            for(int LinkedNode : graph[nodeIndex]) {
                //방문처리 안된노드는 스택에 넣고 방문처리
                if(!visited[LinkedNode]) {
                    stack.push(LinkedNode);
                    visited[LinkedNode] = true;
                }
            }
        }
    }
}

재귀를 이용한 DFS (java)

package DFS_BFS;

public class RecursionDFS {

    // 방문처리에 사용할 배열
    static boolean[] visited = new boolean[9];

    // 그래프의 연결상태를 2차원 배열로 표현
    // 인덱스가 각각의 노드번호가 되고 0번 인덱스는 아무것도 없는 상태
    static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};

    public static void main(String[] args) {
        dfs(1);
    }

    static void dfs(int nodeIndex) {
        // 해당 노드 방문처리
        visited[nodeIndex] = true;
        System.out.print(nodeIndex + " - > ");
        
        // 해당 노드에 인접한 노드 순회
        for(int node : graph[nodeIndex]) {
            //인접한 노드중 방문처리 안된게 있다면 재귀호출
            if(!visited[node]) {
                dfs(node);
            }
        }
    }
}

참고자료
나동빈, 「이것이 코딩테스트다」
소스코드 : [Algorithm] DFS (Depth-first Search)를 Java로 구현해보자!