『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

깊이 우선 탐색 DFS

• 깊이 우선 탐색(DFS; depth-first search)은 그래프 완전 탐색 기법 중 하나이다.
• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
• 깊이 우선 탐색을 표로 정리하면 다음과 같다.
  • V: 노드 개수, E: 에지 개수

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

• 깊이 우선 탐색을 응용하여 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제를 풀 수 있다.
• 실제 구현 시 재귀 함수를 이용하므로 Stack Overflow에 유의해야 한다.

핵심 이론

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

동작

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
   • 필요한 초기 작업은 다음과 같다.
     • 인접 리스트로 그래프 표현하기
     • 방문 배열 초기화하기 (방문 시 T, 미방문 시 F로 초기화)
     • 시작 노드 스택에 삽입하기 (시작점 삽입)
2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
   • pop으로 노드를 꺼낸 후, 꺼낸 노드를 탐색 순서에 기입한다.
   • 인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크한다.
3. 스택 자료구조에 값이 없을 때까지 반복하기
   • 스택 자료구조에 값이 없을 때까지 1~2번 과정을 반복한다.
   • 이때, 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심이다.
   • 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴봐야 한다.

구현 코드

private static void mySource() throws IOException {

    ...

    boolean[] visited = new boolean[N];

    // 인접 리스트
    ArrayList<Integer>[] array = new ArrayList[N];
    for (int i = 0; i < array.length; i++) {
        array[i] = new ArrayList<Integer>();
    }

    for (int i = 0; i < M; i++) {
        int node = 노드;
        int next = node와 연결된 노드;

        // 방향 없는 그래프므로 양쪽 노드에 모두 연결
        array[node-1].add(next-1);
        array[next-1].add(node-1);
    }

    // 탐색 돌면서 연결 요소 카운팅
    int count = 0;
    for (int i = 0; i < array.length; i++) {
        // 방문한 적 없으면 탐색 시작
        if(!visited[i]) {
            count++;
            myDFS(visited, array, i);
        }
    }

    System.out.println(count);
}

private static void myDFS(boolean[] visited, ArrayList<Integer>[] array, int i) {
    // 방문한 적 있으면 탐색 종료
    if (visited[i]) {
        return;
    }

    // 방문했으므로 표시
    visited[i] = true;

    // 인접 노드 탐색
    for (int node : array[i]) {
        myDFS(visited, array, node);
    }
}

---

너비 우선 탐색 BFS

• 너비 우선 탐색(BFS; breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나이다.
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
• 깊이 우선 탐색을 표로 정리하면 다음과 같다.
  • V: 노드 개수, E: 에지 개수

기능	특징	시간복잡도
그래프 완전 탐색	* FIFO 탐색 * Queue 자료구조 이용	O(V+E)

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

핵심 이론

1. 시작할 노드를 정한 후 사용할 자료구조 초기화
   • 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.
   • 그래프는 인접 리스트로 표현한다.
   • DFS와의 차이점은 탐색을 위해 큐를 사용한다는 점이다.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
   • 큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.
   • 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.
   • 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복하기
   • 큐에 노드가 없을 때까지 1~2번 과정을 반복한다.

구현 코드

private static void BFS(int i, int j) {
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[] {i, j});
    while (!queue.isEmpty()) {
        int now[] = queue.poll();
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int x = now[0] + dx[k];
            int y = now[1] + dy[k];
            if (x >=0 && y>=0 && x<N && y<M) {
                if (A[x][y] != 0 && !visited[x][y]) {
                    visited[x][y] = true;
                    A[x][y] = A[now[0]][now[1]] + 1;
                    queue.add(new int[] {x, y});
                }
            }
        }
    }
}

---

이진 탐색 Binary Search

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

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

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

핵심 이론

• 이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복한다.
  1. 현재 데이터셋의 중앙값(median)을 선택한다.
  2. 중앙값 > 타깃 데이터(target data)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
  3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
  4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

구현 코드

int start = 0;
int end = A.length -1;

while (start <= end) {
    int mid_index = (start + end) / 2;
    int mid_value = A[mid_index];

    if(mid_value > target) {
        end = mid_index-1;
    }
    else if (mid_value < target) {
        start = mid_index+1;
    }
    else {
        find = true;
    }
}

---

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런