[Java | 알고리즘] DFS - 깊이 우선 탐색

DFS

• 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
• 모든 노드를 방문할 때 사용
• 단순 검색 속도는 BFS가 더 빠름

특징

• 자기 자신을 호출하는 순환 알고리즘의 형태
• 방문한 노드 여부 반드시 검사
• 스택 사용해 구현
• 거리 계산할 땐 사용할 수 없음

사용 예시

• 그래프 전체 탐색
• 전위 순회(표기법)
• 미로 탐색
• 그래프 사이클 찾기
• 그래프 연결 요소 찾기

수행 과정

1. 시작 노드 방문 (방문한 노드는 체크 시작)
   • 시작 노드를 스택에 삽입
2. 방문한 노드에 연결된 노드 중 방문하지 않은 노드 방문
   • 방문하는 노드들 순서대로 스택에 삽입
3. 현재 노드 주변에 더 이상 방문하지 않은 노드가 없다면 스택에서 꺼내는 순서대로 backtracking
4. backtracking한 노드 주변에 방문하지 않은 노드가 있다면 2번 반복
5. 스택이 빈 상태로 시작 노드까지 다시 돌아간다면 탐색 종료

구현

인접행렬 + 재귀 호출 방법

public class DFS {
    static StringBuilder sb = new StringBuilder();
    static boolean[] visited;
    static int[][] graph;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());  //node
        int M = Integer.parseInt(st.nextToken());  // edge
        int V = Integer.parseInt(st.nextToken());  // start

        graph = new int[N+1][N+1];
        visited = new boolean[graph.length];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 인접행렬 방법
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        dfs(V);
        System.out.println(sb);

    }

    public static void dfs(int start) {
        // 재귀 방법
        visited[start] = true;
        sb.append(start + " ");

        for (int i = 0; i <= N; i++) {
            if (graph[start][i] == 1 && !visited[i]) {
                visited[i] = true;
                dfs(i);
            }
        }
    }
}

인접행렬 + 스택 사용 방법

public class DFS {
    static StringBuilder sb = new StringBuilder();
    static boolean[] visited;
    static int[][] graph;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());  //node
        int M = Integer.parseInt(st.nextToken());  // edge
        int V = Integer.parseInt(st.nextToken());  // start

        graph = new int[N+1][N+1];
        visited = new boolean[graph.length];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 인접행렬 방법
            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        dfs(V);
        System.out.println(sb);

    }

    public static void dfs(int start) {
        Stack<Integer> stack = new Stack<>();

        stack.add(start);

        while (!stack.isEmpty()) {
            start = stack.pop();
            if (visited[start]) {
                continue;
            }
            visited[start] = true;
            sb.append(start + " ");

            // 인접한 정점을 스택에 넣을 때, 번호가 작은 것부터 넣도록
            for (int i = N; i >= 1; i--) {
                if (graph[start][i] == 1 && !visited[i]) {
                    stack.add(i);
                }
            }
        }
    }
}

인접 리스트 + 스택 사용 방법

public class DFS {
	// 인접 리스트
    static int[][] graph = {
            {},
            {2,3,7},
            {1,3,5},
            {1,2},
            {6,8},
            {2},
            {4,7,8},
            {1,6},
            {4,6}
    };
    public static void main(String[] args) {
    	// 1 7 6 8 4 3 2 5
        System.out.println(dfs(1));
    }
    static String dfs(int start) {
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.length];

        stack.add(start);

        while (!stack.isEmpty()) {
            start = stack.pop();
            if (visited[start]) {
                continue;
            }
            visited[start] = true;
            sb.append(start + " ");

            // 현재 노드와 연결된 모든 인접 노드 탐색  => 현재 노드가 1일 때
            // graph[start]: 현재 노드와 연결된 노드들의 배열  => 인접한 노드는 2, 3, 7
            // graph[start].length: 현재 노드와 연결된 노드들의 개수
            for (int i = 0; i < graph[start].length; i++) {
                // 현재 노드와 인접한 모든 노드 가져옴  => 처음에는 인접 노드 2가 가져와짐
                int adjacentNode = graph[start][i];
                // 인접 노드가 아직 방문하지 않았으면 스택에 추가
                if (!visited[adjacentNode]) {
                    stack.add(adjacentNode);
                }
            }

        }
        return sb.toString();
    }
}

1. stack.add(start);: 시작 노드 1을 스택에 추가
2. while (!stack.isEmpty()) {: 스택이 비어있지 않으므로 while 루프가 실행
3. start = stack.pop();: 스택에서 1이 꺼내지고, 현재 탐색할 노드는 1
4. visited[start] = true;: 현재 노드인 1을 방문했다고 표시
5. for (int i = 0; i < graph[start].length; i++) {: 현재 노드와 인접한 모든 노드를 확인하기 위해 반복문을 시작(현재 노드인 1과 연결된 인접 노드: 2, 3, 7)
6. int adjacentNode = graph[start][i];: 현재 반복문에서 확인하고 있는 인접 노드를 가져옴 (처음에는 인접 노드 2가 가져와짐)
7. if (!visited[adjacentNode]) { stack.add(adjacentNode); }: 인접 노드가 아직 방문하지 않은 노드라면 스택에 추가 (현재 인접 노드 2는 방문하지 않았으므로 스택에 추가)
8. 이후 반복문이 계속 실행 (인접 노드 3이 스택에 추가되고, 마지막으로 인접 노드 7이 스택에 추가)
9. 스택이 비어있지 않으므로 다시 while 루프가 실행
10. 스택에서 7을 꺼내서 현재 탐색할 노드로 설정 (7번 노드와 연결된 인접 노드는 1, 6)
11. 이미 방문한 1 노드는 스택에 추가되지 않고 넘어가고, 6을 스택에 추가 후 탐색
12. 위의 과정 반복 후 스택이 비면 while 루프를 종료