탐색

DFS(깊이 우선 탐색)

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

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

 

** 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 '스택 오버플로(stack overflow)'에 유의해야 함. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있음.

 

핵심 이론

한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현. 또한, DFS의 탐색 방식은 후입선출 특성을 가지므로 스택 성질을 갖는 재귀 함수로 많이 구현.

 

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

- DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다.

 

⭐2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입

- pop을 수행하여 노드를 꺼냄. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크.

 

3. 스택 자료구조에 값이 없을 때까지 반복하기

- 앞선 과정을 스택 자료구조에 값이 없을 때까지 반복. 이 때 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심.

 

DFS 문제 풀이

- 백준 11724

package boj11724;

import java.util.*;
public class Main {

    static int[][] graph;
    static boolean[] visit;

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

        int N = scan.nextInt();
        int M = scan.nextInt();

        graph = new int[N+1][N+1];
        visit = new boolean[N+1];
        int answer = 0;

        for(int i = 0; i < M; i++) {
            int u = scan.nextInt();
            int v = scan.nextInt();
            graph[u][v] = 1;
            graph[v][u] = 1;
        }

        for(int i = 1; i <= N; i++) {
            if(!visit[i]) {
                dfs(N, i);
                answer++;
            }
        }

        System.out.println(answer);


    }

    public static void dfs(int N, int start) {
        visit[start] = true;
        for(int i = 1; i <= N; i++) {
            if(!visit[i] && graph[start][i] == 1) {
                dfs(N, i);
            }
        }
    }
}

---

BFS(너비 우선 탐색)

너비 우선 탐색도 그래프를 완전 탐색하는 방법 중 하나. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘.

기능	특징	시간 복잡도(노드 수 : V, 에지 수 : E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V + E)

 

** 너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장.

 

핵심 이론

 

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

BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요. 그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일. 그러나 탐색을 위해 스택이 아닌 큐를 사용.

시작 노드를 큐에 삽입하며 방문 배열에 체크

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입. 이 때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않음. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록.

1을 꺼내면서 탐색 순서에 1을 기록하고 인접 노드 3, 2를 큐에 삽입하며 방문배열에 체크

 

3. 큐 자료구조에 값이 없을 때까지 반복하기

큐에 노드가 없을 때까지 앞선 과정을 반복. 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름을 확인.

 

BFS 문제 풀이

- 백준 2178

package boj2178;

import java.util.*;
public class Main {

    static int[][]graph;
    static boolean[][]visit;

    static class Pair{
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

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

        int N = scan.nextInt();
        int M = scan.nextInt();
        scan.nextLine();

        graph = new int[N+1][M+1];
        visit = new boolean[N+1][M+1];

        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};

        for(int i = 1; i <= N; i++) {
            String input = scan.nextLine();
            for(int j = 1; j <= M; j++) {
                graph[i][j] = Character.getNumericValue(input.charAt(j-1));
            }
        }

        Queue<Pair> q = new LinkedList<>();

        q.offer(new Pair(1,1));
        visit[1][1] = true;
        Boolean flag = false;

        while(!q.isEmpty()) {
            for(int i = 0; i < q.size(); i++) {
                Pair num = q.poll();

                if(num.x == N && num.y == M) {
                    flag = true;
                    break;
                }

                for(int j = 0; j < 4; j++) {
                    int nx = num.x + dx[j];
                    int ny = num.y + dy[j];

                    if(nx > 0 && ny > 0 && nx <= N && ny <= M) {
                        if(!visit[nx][ny] && graph[nx][ny] == 1) {
                            visit[nx][ny] = true;
                            graph[nx][ny] = graph[num.x][num.y] + 1;
                            q.offer(new Pair(nx, ny));
                        }
                    }
                }
            }
            if(flag) break;
        }
        System.out.println(graph[N][M]);
    }
}

 

 

DFS vs BFS

DFS가 스택을 사용하고 BFS가 큐를 사용하는 이유

---

이진 탐색(Binary Search)

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음.

기능	특징	시간 복잡도
타깃 데이터 탐색	중앙값 비교를 통한 대상 축소 방식	O(logN)

 

이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘. 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역.

 

핵심 이론

이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복

 

이진 탐색 과정

1. 현재 데이터셋의 중앙값(median)을 선택 -> 중앙값의 인덱스 = (start + end) / 2
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 -> end = median - 1
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택 -> start = median + 1
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다

** start = 탐색할 배열의 첫 인덱스 값 / end = 탐색할 배열의 마지막 인덱스 값

 

** 이진 탐색을 사용하면 N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있음. 단, 이진 탐색은 데이터가 정렬되어 있어야 함.

 

이진 탐색 문제 풀이

- 백준 1920

package boj1920;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();
        int[] nArr = new int[N];

        for(int i = 0; i < N; i++){
            nArr[i] = scan.nextInt();
        }

        Arrays.sort(nArr);

        int M = scan.nextInt();
        int[] mArr = new int[M];


        int m;
        int result = 0;

        for(int i = 0; i < M; i++) {
            int start = 0;
            int end = nArr.length - 1;
            result = 0;
            mArr[i] = scan.nextInt();
//            System.out.println(mArr[i]);
            while(start <= end) {
                m = (start + end) / 2;
                if(mArr[i] < nArr[m]) {
                    end = m - 1; // 왼쪽 데이터셋 선택
                } else if(mArr[i] > nArr[m]) {
                    start = m + 1; // 오른쪽 데이터셋 선택
                } else {
                    result = 1;
                    break;
                }
            }
            System.out.println(result);
        }
    }
}