[Algorithm] 탐색 알고리즘

탐색 알고리즘

탐색 알고리즘은 주로 그래프, 트리 등의 데이터 구조 내부에서 특정 데이터를 찾기 위해 사용된다.
데이터의 구조, 크기나 특성, 정렬 여부, 탐색 속도 등 다양한 요소에 따라 알고리즘의 적합성이 달라지기 때문에 특정 상황에서 가장 효율적인 탐색 방법을 고려하여 알고리즘을 적용해야 한다.

1. Linear Search (선형 탐색)

• 데이터를 처음부터 끝까지 순차적으로 탐색하여 원하는 데이터를 탐색한다.
• 정렬 여부와 상관 없이 모든 데이터에 대해 탐색을 수행한다.
• 시간복잡도는 최선의 경우 O(1), 최악의 경우 O(n)

2. Binary Search (이진 탐색)

• 데이터를 중간값과 비교하여 탐색 범위를 반으로 줄여나가 원하는 데이터를 탐색한다.
• 정렬된 데이터에만 적용 가능하다.
• 시간 복잡도는 O(log n)

3. Exhaustive Search (완전 탐색)

• 가능한 모든 경우의 수를 체크해보며 최적의 결과를 탐색한다.
• 복잡한 알고리즘을 적용하기 전에 모든 가능성을 탐색하여 문제를 해결할 수 있는 가장 확실한 방법이다.

3-1. DFS(Depth-First Search, 깊이 우선 탐색)

• 그래프, 트리 구조에서 주로 사용된다.
• 한 노드에서 시작해 연결된 모든 노드를 탐색한 후, 더 이상 연결된 노드가 없을 때 그 전 노드로 돌아가 다시 인접한 노드를 따라 탐색한다.
• 모든 경로를 방문해야 할 경우에 적합하다.
• 스택(Stack)이나, 재귀(Recursion) 호출을 통해 구현 가능하다.
• 인접 행렬의 시간 복잡도는 O(접점^2), 인접 리스트의 시간 복잡도는 O(접점+간선)
  

스택으로 구현한 DFS

public class StackDFS {
    private LinkedList<Integer>[] adj; // 그래프의 인접 리스트
    private boolean[] visited; // 방문 여부를 체크할 배열

    // 그래프 초기화
    public StackDFS(int vertices) {
        adj = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            adj[i] = new LinkedList<>();
        }
    }

	// source번째 LinkedList에 dest 간선 추가
    void addEdge(int source, int dest) {
        adj[source].add(dest);
    }

    void DFS(int vertex) {
        Stack<Integer> stack = new Stack<>();
        stack.push(vertex); // 시작 노드 push
        while (!stack.isEmpty()) {
            int current = stack.pop(); // 현재 노드 pop
            if (!visited[current]) {
                visited[current] = true; // 방문한 노드 방문 처리
                System.out.print(current + " ");
                for (int dest : adj[current]) {
                    if (!visited[dest]) {
                        stack.push(dest); // 인접한 모든 노드를 스택에 추가
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        StackDFS g = new StackDFS(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        
        System.out.println("DFS starting from vertex 2:");
        g.DFS(2);
    }
}

재귀로 구현한 DFS

public class RecursiveDFS {
    private LinkedList<Integer>[] adj; // 그래프의 인접 리스트
    private boolean[] visited; // 방문 여부를 체크할 배열

    public RecursiveDFS(int vertices) {
        adj = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            adj[i] = new LinkedList<>();
        }
    }
    
	// source번째 LinkedList에 dest 간선 추가
    void addEdge(int source, int dest) {
        adj[source].add(dest);
    }

    void DFS(int vertex) {
        visited[vertex] = true; // 현재 노드 방문 처리
        System.out.print(vertex + " ");
        for (int dest : adj[vertex]) { // 현재 노드와 인접한 모든 노드에 대해
            if (!visited[dest]) { 
                DFS(dest); // 방문하지 않았다면 재귀 호출
            }
        }
    }

    public static void main(String[] args) {
        RecursiveDFS g = new RecursiveDFS(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        
        System.out.println("DFS starting from vertex 2:");
        g.DFS(2);
    }
}

3-2. BFS(Breadth-First Search, 너비 우선 탐색)

• 그래프, 트리 구조에서 주로 사용된다.
• 시작 노드에서 가장 인접한 노드를 먼저 탐색하고, 그 다음으로 인접한 노드들을 모든 노드를 방문할 때까지 차례로 방문한다.
• 최소 비용이 우선일 경우에 적합하다.
• 큐(Queue)를 통해 구현 가능하다.
• 인접 행렬의 시간 복잡도는 O(접점^2), 인접 리스트의 시간 복잡도는 O(접점+간선)
  

큐로 구현한 BFS

public class QueueBFS {
    private LinkedList<Integer>[] adj; // 그래프의 인접 리스트
    private boolean[] visited; // 방문 여부를 체크할 배열

    public QueueBFS(int vertices) {
        adj = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++) {
            adj[i] = new LinkedList<>();
        }
    }
    
	// source번째 LinkedList에 dest 간선 추가
    void addEdge(int source, int dest) {
        adj[source].add(dest);
    }

    void BFS(int vertex) {
        Queue<Integer> queue = new LinkedList<>();
        visited[vertex] = true;
        queue.add(vertex);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");
            for (int dest : adj[current]) { // 인접한 모든 노드 확인
                if (!visited[dest]) {
                    visited[dest] = true; // 방문한 노드 방문 처리
                    queue.add(dest); // 아직 방문하지 않은 노드 모두 큐에 삽입
                }
            }
        }
    }

    public static void main(String[] args) {
        QueueBFS g = new QueueBFS(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        
        System.out.println("BFS starting from vertex 2:");
        g.BFS(2);
    }
}

참고
[Algorithm] DFS (Depth-first Search)를 Java로 구현해보자!
[Algorithm] BFS(Breadth-first search)를 Java로 구현해보자!