깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)

DFS(Depth-First Search) 는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

DFS 는 Stack 자료구조를 사용하며 Stack 을 이용하기 때문에 재귀 함수를 이용하면 쉽게 DFS 구현을 할 수 있다.

재귀와 Stack 에 대해서 잘 모르겠으면 해당 링크를 통해서 배우고 오자.

동작 과정

Step1

Step1. 시작 노드를 스택에 넣고 방문 처리한다.

Step2

Step2. 방문하지 않은 인접 노드 중에서 번호가 가장 낮은 곳을 방문하고 해당 노드를 스택에 넣어 방문 처리 한다.

Step3

Step3. 위 과정을 반복한다.

구현

public class Main {

    public static boolean[] visited = new boolean[9];
    public static List<List<Integer>> graph = new ArrayList<>();

    // Depth-First Search 
    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) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);

        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(5);
        graph.get(2).add(8);

        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(4);
        graph.get(3).add(6);

        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(7);

        // dfs 시작 
        dfs(1);
    }
}

References

• 이것이 코딩 테스트다