깊이 우선 탐색 DFS 개념과 작동 방식

금일 프로그래머스에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 관련 알고리즘 문제를 풀다가 막혀버린 두부입니다. 이렇게 쉬워보이는 알고리즘도 못 푸니까 스스로에게 화가 나네요. 잡담은 여기까지하고 깊이 우선 탐색의 개념과 작동 방식에 대해서 알아보겠습니다.

DFS (Depth-First-Search)

깊이 우선 탐색이라고 불리고 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

특징

• 자기 자신을 호출하는 순환 알고리즘 (재귀 함수, 스택)
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야함
• 탐색 하는 중에 더 이상 갈 수 없는 곳까지 가게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행함
• 모든 노드를 방문하고자 할 때 사용함
• 너비우선탐색(bfs)에 비해서 간단하지만 검색 속도가 느림

 

DFS 그래프 예시

인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순부터 처리함

1. 시작 노드 '1'을 스택에 삽입

2. 스택의 최상단 노드 '1'에 방문하지 않은 인접 노드 '2', '3' '8' 중에서 가장 작은 노드 '2'를 스택에 삽입

3. 스택의 최상단 노드 '2'에 방문하지 않은 인접 노드 '7'을 스택에 삽입

4. 스택의 최상단 노드 '7'에 방문하지 않은 인접 노드 '6'과 '8' 중에서 가장 작은 노드 '6'을 스택에 삽입

5. 스택의 최상단 노드 '6'에 방문하지 않은 인접 노드가 없으므로 스택에서 '6'을 꺼낸 후, '7'로 돌아가서 방문하지 않은 인접 노드인 '8'을 스택에 삽입

6. 최상단 노드 '8'에 방문하지 않은 인접 노드가 없으므로 스택에서 '8'을 꺼낸 후, '7', '2', '1'까지 돌아온 후에 방문하지 않은 인접 노드 '3'을 스택에 삽입

7. 최상단 노드 '3'에 방문하지 않은 인접 노드 '4', '5' 중 가장 작은 노드 '4'를 스택에 삽입

8. 스택의 최상단 노드 '4'에 방문하지 않은 인접 노드가 없으므로 '3'으로 돌아온 후, 방문하지 않은 인접 노드 '5'를 스택에 삽입

9. 남아 있는 노드에 방문하지 않은 인접 노드가 없으므르 모든 노드를 차례대로 꺼내면서 아래의 순서대로 탐색 완료.

1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

장점

• 구현이 너비 우선 탐색(bfs)보다 간단함
• 현재 경로상의 노드들만 기억하면 되므로, 저장 공간의 수요가 적음

단점

• 모든 정점, 간선을 탐색하므로 검색 속도가 느림
• 목표에 이르는 경로가 다수인 경우 구한 해가 최적이 아닐 수 있음

재귀 함수를 이용한 dfs 구현

public class DFSExamRecursion {
    // 각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
    public static boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
    // 각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
    public static int[][] graph = {{},
        {2, 3, 8},
        {1, 7},
        {1, 4, 5},
        {3, 5},
        {3, 4},
        {7},
        {2, 6, 8},
        {1, 7}};
    
    public static void main(String[] args){
        int start = 1; // 시작 노드
        dfs(start);
    }
    
    /*
	 * dfs 알고리즘을 수행하는 함수
	 * @param v 탐색할 노드
    */
    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 구현

public class DFS_Stack {
    public static void main(String[] args){
        
        // 각 노드가 연결된 정보를 2차원 배열 자료형으로 표현
        int [][]graph = {{},
            {2, 3, 8},
            {1, 7},
            {1, 4, 5},
            {3, 5},
            {3, 4},
            {7},
            {2, 6, 8},
            {1, 7}};
        
        // 각 노드가 방문된 정보를 1차원 배열 자료형으로 표현
        boolean [] visited = {false, false, false ,false ,false ,false ,false ,false, false};
        
        // 정의된 DFS 함수 호출
        DFS_Stack dfsExam = new DFS_Stack();
        dfsExam.dfs(graph, 1, visited);
    }
    
    /*
     * dfs 메서드
     *  @param graph 노드 연결 정보를 저장
     *  @param v 방문을 시작하는 최상단 노드의 위치
     *  @param visited 노드 방문 정보를 저장
    */
    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();
        }
    }
}