[알고리즘] DFS (Java)

 

DFS란?

 

Depth-First Search, 깊이 우선 탐색

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

 

동작 과정

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

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

 

자세히 살펴보기

 

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

 

1. 시작 노드인 '1'을 스택에 삽입하고 방문 처리를 한다.

 

2. 스택의 최상단 노드인 '1’에 방문하지 않은 인접 노드 ‘2’，‘3’，‘8’이 있다.

이 중에서 가장 작은 노드 인 ‘2’를 스택에 넣고 방문 처리를 한다.

 

3. 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드 ‘7’이 있다.

따라서 ‘7’ 번 노드를 스택에 넣고 방문 처리를 한다. 

 

4. 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘6’과 ‘8’이 있다.

이 중에서 가장 작은 노드인 ‘6’을 스택에 넣고 방문 처리를 한다.

 

5. 스택의 최상단 노드인 ‘6’에 방문하지 않은 인접 노드가 없다.

따라서 스택에서 ‘6’번 노드를 꺼낸다.

 

6. 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘8’이 있다.

따라서 ‘8’ 번 노드를 스택에 넣고 방문 처리를 한다.

 

7. 스택의 최상단 노드인 ‘8’에 방문하지 않은 인접 노드가 없다.

따라서 스택에서 ‘8’번 노드를 꺼낸다.

 

8. 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드가 없다.

따라서 스택에서 ‘7’ 번 노드를 꺼낸다.

 

9. 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드가 없다.

따라서 스택에서 ‘2'번 노드를 꺼낸다.

 

10. 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘3’을 스택에 넣고 방문 처리한다.

 

11. 스택의 최상단 노드인 ‘3’에 방문하지 않은 인접 노드 ‘4’와 ‘5’가 있다.

이 중에서 가장 작은 노드인 ‘4’를 스택에 넣고 방문 처리를 한다.

 

12. 스택의 최상단 노드인 ‘4’에 방문하지 않은 인접 노드 ‘5’가 있다.

따라서 ‘5’ 번 노드를 스택에 넣고 방문 처리를 한다.

 

13. 남아 있는 노드에 방문하지 않은 인접 노드가 없다.

따라서 모든 노드를 차례대로 꺼낸다.

 

노드 탐색 순서

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

 

특징

 

1. 스택 자료구조에 기초한다. -> 재귀 함수로 구현 가능

2. 데이터의 개수가 N개인 경우 O(N)의 시간복잡도를 가진다.

 

재귀함수로 구현한 코드

 

public class DFS {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph;

    // DFS 함수 정의
    public static void dfs(int x) {
        visited[x] = true;
        System.out.print(x + " ");

        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 정의
        graph = new ArrayList<>() {{
            add(new ArrayList<>(List.of()));
            add(new ArrayList<>(List.of(2, 3, 8)));
            add(new ArrayList<>(List.of(1, 7)));
            add(new ArrayList<>(List.of(1, 4, 5)));
            add(new ArrayList<>(List.of(3, 5)));
            add(new ArrayList<>(List.of(3, 4)));
            add(new ArrayList<>(List.of(7)));
            add(new ArrayList<>(List.of(2, 6, 8)));
            add(new ArrayList<>(List.of(1, 7)));
        }};

        // 정의된 DFS 함수 호출
        dfs(1);
    }
}

 

스택으로 구현한 코드

 

public class DFS {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static List<Integer> result = new ArrayList<>();

    static String dfs(int start) {
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        boolean hasNext;

        stack.push(start);
        visited[start] = true;
        result.add(start);

        while (!stack.isEmpty()) {
            Integer top = stack.peek();
            hasNext = false;

            for (int i = 0; i < graph.get(top).size(); i++) {
                int num = graph.get(top).get(i);

                if (!visited[num]) {
                    stack.push(num);
                    visited[num] = true;
                    hasNext = true;
                    result.add(num);
                    break;
                }
            }

            // 방문하지 않은 인접노드가 없는 경우
            if (!hasNext) {
                stack.pop();
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        // 인접리스트
        graph = new ArrayList<>() {{
            add(new ArrayList<>(List.of()));
            add(new ArrayList<>(List.of(2, 3, 8)));
            add(new ArrayList<>(List.of(1, 7)));
            add(new ArrayList<>(List.of(1, 4, 5)));
            add(new ArrayList<>(List.of(3, 5)));
            add(new ArrayList<>(List.of(3, 4)));
            add(new ArrayList<>(List.of(7)));
            add(new ArrayList<>(List.of(2, 6, 8)));
            add(new ArrayList<>(List.of(1, 7)));
        }};

        visited = new boolean[graph.size()];

        System.out.println(dfs(1));
    }
}

 

출력 결과

1 2 7 6 8 3 4 5

 

 

Reference

이것이 코딩테스트다 - 나동빈