깊이 우선 탐색(DFS) - JAVA

깊이 우선 탐색

깊이 우선 탐색은 영어로 DFS (Depth First Search) 라 표현하며, 그래프를 탐색하는데 깊이를 우선으로 하여 탐색한다는 뜻이다. DFS 탐색을 위해선 스택이라는 자료구조가 필요하다. 스택을 사용한 DFS 탐색 방법은 아래와 같다.

DFS 순서

1. 시작노드를 스택에 담는다.
2. 스택의 최상단(top)에 있는 노드를 기준으로 방문되지 않은 노드중 가장 가까운 노드를 방문하고 스택에 삽입한다.
3. 더 이상 진행할 수 없을 때 까지 2번 과정을 반복한다.
4. 인접노드가 모두 방문되어 2번 과정이 불가능하다면 스택에서 pop을 하여 맨 위의 값을 제거한다.
5. pop된 후 스택의 top의 노드를 기준으로 2 ~ 4번을 반복한다.
6. 스택이 비게된다면 탐색이 완료된다.

예시

예시로 그래프가 아래와 같을 경우 (무방향 그래프, 숫자가 낮은 노드부터 탐색)

DFS로 탐색을 진행한다면 1 -> 2 -> 3 -> 5 -> 6 -> 9 -> 8 -> 7 -> 4 순 으로 탐색을 진행하게 된다.

코드

DFS 탐색을 코드로 구현할 땐 재귀를 사용하여 구현하거나 스택을 사용하여 구현한다.

package pjh5365.graph;

import java.util.Stack;

public class DFS {

    static boolean[] visited1 = new boolean[10];  // 9번 노드까지 있으므로 0빼고 사용하기 위해 10개 필요 (스택에서 사용)
    static boolean[] visited2 = new boolean[10];  // 9번 노드까지 있으므로 0빼고 사용하기 위해 10개 필요 (재귀에서 사용)

    static int[][] graph = {    // 배열별로 자신이 가르키는 노드를 가짐 (양방향 그래프임)
            {}, // 0번 사용하지 않음
            {2, 3, 4},  // 1번 노드가 가르키는 노드는 2, 3, 4
            {1},  // 2번 노드가 가르키는 노드는 1
            {1, 5}, // 3번 노드가 가르키는 노드는 1, 5
            {1}, // 4번 노드가 가르키는 노드는 1
            {3, 6, 7},  // 5번 노드가 가르키는 노드는 3, 6, 7
            {5, 9},    // 6번 노드가 가르키는 노드는 5, 9
            {5}, // 7번 노드가 가르키는 노드는 5
            {9},  // 8번 노드가 가르키는 노드는 9
            {6, 8}  // 9번 노드가 가르키는 노드는 6, 8
    };

    public static void main(String[] args) {
        System.out.println("DFS 스택사용");
        dfsStack(1);
        System.out.println("\nDFS 재귀사용");
        dfsRecursion(1);
    }

    static void dfsStack(int start) {  // 스택을 사용해 DFS 탐색
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(start); // 시작인덱스를 스택에 삽입
        visited1[start] = true; // 시작인덱스는 방문함
        System.out.print(start + " -> ");

        while(!stack.isEmpty()) {  // 스택에 값이 존재한다면 계속
            int i = 0;  // 탐색하는 노드의 인접노드를 탐색하기 위한 변수
            int peek = stack.peek();   // 스택의 최상위 값 가져오기

            for(; i < graph[peek].length; i++) {    // 최상단의 인접노드를 탐색
                if(!visited1[graph[peek][i]]) {    // 방문하지 않았다면
                    visited1[graph[peek][i]] = true; // 방문 표시
                    stack.push(graph[peek][i]); // 스택에 삽입
                    System.out.print(graph[peek][i] + " -> ");    // 방문했으니 출력
                    peek = stack.peek();    // 스택의 최상위 값 다시가져오기
                    i = -1;  // 스택의 최상위 값이 변경되었으니 i 는 다시 0으로 변경하기 위해 -1로 변경 (해당 구문이 끝난 후 for 문에 의한 증가를 하므로)
                }
            }
            stack.pop();    // 탐색이 완료되어 for 문을 나와 해당 노드는 더 이상 필요하지 않으므로 pop
        }
    }

    static void dfsRecursion(int start) {   // 재귀를 사용한 DFS 탐색
        if(!visited2[start]) {   // 해당 노드가 방문되지 않았다면
            System.out.print(start + " -> "); // 출력으로 방문확인
            visited2[start] = true;  // 방문 표시
            for(int i = 0; i < graph[start].length; i++)
                dfsRecursion(graph[start][i]);    // 인접노드에 대한 dfs 탐색
        }
    }
}

결과는 아래와 같이 나온다.