깊이 우선 탐색 (DFS : Depth-First Search)

깊이 우선 탐색 (DFS)은 그래프 완전 탐색 기법 중 하나이다.

깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
그래프 완전 탐색	재귀 함수로 구현 스택 자료구조 이용	O(V+E)

 

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 한다.

깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

 

깊이 우선 탐색 DFS의 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인전 리스트로 표현한다. 그리고 DFS 탐색 방식은 후입선출 특성을 가지므로 스택을 사용한다.

 

참고할 문제

 

https://www.acmicpc.net/problem/2023

 

https://www.acmicpc.net/problem/13023

// 백준 13023번 문제 코드

import java.util.*;
import java.io.*;
// 최소 5번의 일직선 연결이 존재하는지 확인하는 문제 -> 재귀 사용 
public class Main {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static boolean arrive;

    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =
                new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        A = new ArrayList[n];
        visited = new boolean[n];
        arrive = false;

        // 리스트 초기화
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }

        // 리스트에 데이터 집어 넣기
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            A[x].add(y);
            A[y].add(x);
        }

        for(int i = 0 ; i < n; i++) {
            DFS(i, 1);
            if(arrive) {
                break;
            }
        }
        if(arrive) {
            System.out.println("1");
        } else {
            System.out.println("0");
        }

    }

    private static void DFS(int n, int count) {
        if(count == 5 || arrive) {  // 이미 5번의 최소 연결이 되었을 때 리턴
            arrive = true;
            return;
        }

        visited[n] = true;
        
        for(int i : A[n]) {
            if(!visited[i]) {
                DFS(i, count + 1);
            }
        }
        // 다음 반복문을 실행하기 위해 값 리셋시키기
        visited[n] = false;
    }
}