# 깊이 우선 탐색

### DFS

* 깊이 우선 탐색(DFS)은 그래프 완전 탐색 기법 중 하나다.
* 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
* DFS는 재귀 함수로 구현하고 스택 자료구조를 이용하며 시간 복잡도는 노드 수가 V, 에지 수가 E라고 했을 경우 O(V + E)이다. 이때 스택 오버플로에 유의해야 한다.
* DFS을 응용하여 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬하기 등의 문제를 풀 수 있다.



### **핵심 이론**

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

1.  DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기

    • DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기다.
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
3.  스택 자료구조에 값이 없을 때까지 반복하기

    • 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴봅니다.



#### 초기화

* 원본 그래프
* 인접 리스트
* 방문 배열
* 스택 자료구조에 시작점 더하기&#x20;



### 연결 요소의 개수 구하기&#x20;

#### Question - 11724

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FZ409eWTEpjDbGspANVz8%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-09%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%209.54.54.png?alt=media\&token=6d78b0a2-0802-4798-b1bf-d889758f018a)

#### Code&#x20;

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class N23_P11724_연결_요소의_개수 {

    static ArrayList<Integer>[] A;
    static boolean visited[];

    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 L = Integer.parseInt(st.nextToken());

        A = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i < N + 1; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < L; i++) { // 간선의 길이만큼 반복
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }

        int count = 0;
        for (int i = 1; i < N + 1; i++) { // 실수 i = 0 이라고 했다. ㅂㅅㅂㅅ, N까지라고 했다 ㅅㅂㅅ
            if (!visited[i]) { // 아직 방문하지 않은 경우일 떄
                count++;
                DFS(i);
            }
            // 방문을 했으면 패스한다.
        }
        System.out.println(count);
    }

    static void DFS(int v) {
        if (visited[v]) { // 이미 방문했으면 넘어간다.
            return;
        }
        visited[v] = true; // 방문 안헀으면 방문했다고 변경한다.

        for (int i : A[v]) { // 연결되어 있는 노드들 깊이 우선 탐색을 시작한다.
            if (visited[i] == false) DFS(i); // 만약 하나에 다 연결되어 있으면 여기서 다 돌고 나온다.
        }
    }
}

```

#### Insight

#### Idea

* DFS를 설명할 때는 스택으로 설명했지만 여기서는 재귀함수를 구현하였다. 하지만 재귀 함수는 스택과 같은 방식으로 처리된다.&#x20;

#### reference



### 신기한 소수 찾기

#### Question - 2023

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FUEDA2Y2ehpFopfiSxUx7%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-09%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%209.58.50.png?alt=media\&token=c13e9315-cab4-4ac1-b418-8dea6aad4c23)

#### Code

```java
import java.util.Scanner;

public class N24_P2023_신기한_소수 {

    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);
    }

    static void DFS(int number, int len) {
        if( len == N ) {
            if(isPrime(number)) {
                System.out.println(number);
            }
            return;
        }

        for (int i = 1; i < 10; i++) {
            if (i % 2 == 0) {
                continue;
            }

            // 끝자리가 3, 5, 7, 9 에 대해서 다시 DFS 진행하기
            if (isPrime(number * 10 +i)) {
                DFS(number * 10 + i, len + 1);
            }
        }
    }

    // 소수 판별
    static boolean isPrime(int num) {
        for (int i = 2; i < num / 2; i++)
            if (num % i == 0)
                return false;
        return true;
    }
}


```

#### Insight

#### Idea

* 수학
* 정수론
* 백트랙킹
* 소수 판정

#### reference



### 친구 관계 파악하기&#x20;

#### Question - 13023

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FPgTeKKNI7CY9vRhZ9G9J%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-06-09%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.14.52.png?alt=media\&token=d60ce730-d7fe-427b-9462-09056dd691da)

#### Code

```java
import java.util.ArrayList;
import java.util.Scanner;

public class N25_P13023_친구_관계_파악하기 {

    // 그래프의 연결관계 파악하기
    // 깊이 우선 탐색으로 돌아서 모두 방문이 되었는지 체크하면 될 듯
    // 깊이가 5 이상이면 출력

    static boolean visited[];
    static ArrayList<Integer>[] A;
    static boolean arrive;

    public static void main(String[] args) {

        int N;
        int M;
        arrive = false;

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        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 < M; i++) {
            int S = sc.nextInt();
            int E = sc.nextInt();

            A[S].add(E);
            A[E].add(S);
        }

        for (int i = 0; i < N; i++) {
            DFS(i, 1);
            if (arrive)
                break;
        }

        if (arrive)
            System.out.println("1");
        else
            System.out.println("0");

    }

    public static void DFS(int now, int depth) {
        if (depth == 5 || arrive) {
            arrive = true;
            return;
        }

        visited[now] = true;
        for (int i : A[now]) { 
            if (!visited[i]) {
                DFS(i, depth + 1);
            }
        }
        visited[now] = false;
    }
}


```

#### Insight

#### Idea

#### reference



