[Coding Test] 탐색

Do it! 알고리즘 코딩테스트 with JAVA
인프런 로드맵 보기

---

DFS

DFS(깊이 우선 탐색)이란?

그래프에서 한 방향으로 끝까지 깊이 탐색한 후, 갈 수 없는 지점에 도달하면 백트래킹(backtracking) 하면서 다른 경로를 탐색하는 방식

boolean[] visited = new boolean[graph.length];

public void dfs(int v) {
    visited[v] = true;
    System.out.print(v + " ");
    for (int next : graph[v]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

시간 복잡도

• O(V + E)
• 정점 수: V, 간선 수: E

특징

• 재귀 호출 또는 스택 사용
• 경로 추적, 미로 탐색 등에서 유리
• 순열, 조합 구현 시 많이 사용

---

BFS

BFS(너비 우선 탐색)이란?

루트 노드부터 시작해 인접한 정점들을 먼저 탐색하고, 이후 인접 정점들의 인접 정점을 차례로 탐색하는 방식

동작 예시

boolean[] visited = new boolean[graph.length];
Queue<Integer> queue = new LinkedList<>();

public void bfs(int start) {
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int v = queue.poll();
        System.out.print(v + " ");
        for (int next : graph[v]) {
            if (!visited[next]) {
                queue.offer(next);
                visited[next] = true;
            }
        }
    }
}

시간 복잡도

• O(V + E)
• 정점 수: V, 간선 수: E

특징

• 큐(Queue) 를 사용
• 최단 경로 문제에 유리
• 레벨별 탐색이 가능

---

이진 탐색

이진 탐색이란?

정렬된 배열에서 중간 값을 기준으로 탐색 범위를 절반씩 좁혀가며 값을 찾는 탐색 알고리즘

동작 예시

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 찾지 못한 경우
}

시간 복잡도

• O(log N)

특징

• 배열이 정렬되어 있어야 함
• 색 범위를 절반으로 줄여가므로 빠름