깊이 우선 탐색

DFS

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

핵심 이론

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

DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기
• DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기다.
스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
스택 자료구조에 값이 없을 때까지 반복하기
• 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴봅니다.

초기화

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

연결 요소의 개수 구하기

Question - 11724

Code

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를 설명할 때는 스택으로 설명했지만 여기서는 재귀함수를 구현하였다. 하지만 재귀 함수는 스택과 같은 방식으로 처리된다.

reference

신기한 소수 찾기

Question - 2023

Code

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

친구 관계 파악하기

Question - 13023

Code

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;
    }
}