[알고리즘] 탐색 알고리즘 (feat. DFS와 BFS)

출처: https://namu.wiki/w/너비 우선 탐색

 

코딩테스트를 준비해본 사람이라면 BFS와 DFS 때문에 머리를 싸맨 경험이 한번쯤은 있을 것이다. 

BFS와 DFS는 탐색 알고리즘 중의 하나인데,

탐색 알고리즘이란 데이터 구조(ex. 배열, 트리, 그래프) 내에서 특정 요소를 찾기 위해 사용되는 알고리즘이다. 

 

선형 탐색 (Linear Search)

• 설명: 가장 단순한 형태의 탐색 알고리즘으로, 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색하며 목표 값을 찾는다.
• 시간 복잡도: O(n) (n: 리스트의 크기) 
• 예제 코드: 

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // 목표 값을 찾으면 인덱스를 반환
        }
    }
    return -1; // 목표 값이 없으면 -1 반환
}

// 사용 예제
const array = [1, 2, 3, 4, 5];
console.log(linearSearch(array, 3)); // 2
console.log(linearSearch(array, 6)); // -1

 

이진 탐색 (Binary Search)

• 설명: 정렬된 리스트에서 효율적으로 목표 값을 찾는 알고리즘이다. 리스트의 중간 값을 기준으로 목표 값과 비교하고, 목표 값이 중간 값보다 크면 오른쪽 절반을, 작으면 왼쪽 절반을 탐색한다. 이 과정을 반복해서 목표 값을 찾는다. 
• 시간 복잡도: O(log n) (n: 리스트의 크기)
• 예제 코드:

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid; // 목표 값을 찾으면 인덱스를 반환
        } else if (arr[mid] < target) {
            left = mid + 1; // 오른쪽 절반을 탐색
        } else {
            right = mid - 1; // 왼쪽 절반을 탐색
        }
    }
    return -1; // 목표 값이 없으면 -1 반환
}

// 사용 예제
const sortedArray = [1, 2, 3, 4, 5];
console.log(binarySearch(sortedArray, 3)); // 2
console.log(binarySearch(sortedArray, 6)); // -1

 

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

• 설명: 주어진 그래프에서 시작 노드로부터 출발하여 가능한 한 깊이 탐식을 진행한 후, 더 이상 깊이 갈 수 없을 때 다음 경로를 탐색하는 방식이다.
• 시간 복잡도: O(V+E) (V:노드의 수, E: 간선의 수)
• 적용 분야
  • 경로 찾기: 미로 문제 등에서 출발점에서 도착점까지의 경로를 찾을 때 유용하다. 그러나 최단 경로를 보장하지는 않는다.
  • 사이클 검출: 그래프에서 사이클(순환구조)을 검출하는데 사용된다.
  • 위상 정렬: 유향 그래프에서의 위상 정렬을 수행할 때 사용된다.
  • 강한 연결 요소: 방향 그래프에서 강한 연결 요소를 찾는데 사용된다. 

DFS 작동 방식 

1. 시작 노드 선택: 탐색을 시작할 노드를 선택한다.
2. 방문 표시: 현재 노드를 방문했음을 표시한다.
3. 인접 노드 탐색: 현재 노드와 연결된 인접 노드들을 차례대로 방문한다.
4. 재귀적/반복적 탐색: 인접 노드를 하나씩 방문하면서 더 깊이 탐색을 진행한다. 더 이상 깊이 갈 수 없으면 이전 노드로 되돌아간다.
5. 모든 노드 방문시 종료: 그래프의 모든 노드를 방문하면 탐색을 종료한다. 

DFS 구현 방법(JavaScript)

그래프 생성 

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'G', 'H', 'I'],
  D: ['B', 'E', 'F'],
  E: ['D'],
  F: ['D'],
  G: ['C'],
  H: ['C'],
  I: ['C', 'J'],
  J: ['I']
};

 

재귀적 DFS 

객체를 사용하여 그래프를 표현하고, 각 노드와 그에 연결된 인접 노드를 저장하는 방식이다. 

const dfsRecursive = (graph, node, visited = new Set()) => {
  if (!visited.has(node)) {
    visited.add(node);
    for (let neighbor of graph[node]) {
      dfsRecursive(graph, neighbor, visited);
    }
  }
  return visited;
};

dfsRecursive(graph, "A");

 

반복적 DFS 

스택을 사용하여 구현하는 방식이다.

const dfsIterative = (graph, start) => {
  const visited = [];
  let stack = [];

  stack.push(start);

  while (stack.length > 0) {
    const node = stack.shift();
    if (!visited.includes(node)) {
      visited.push(node);
      stack = [...graph[node], ...stack];
    }
  }
  return visited;
};

dfsIterative(graph, "A") // ['A', 'B', 'D', 'E', 'F', 'C']

 

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

• 설명: 주어진 그래프에서 시작 노드로부터 출발하여 인접한 노드들을 먼저 탐색한 후, 인접 노드의 인접 노드들을 탐색하는 방식이다.
• 시간 복잡도: O(V+E) (V:노드의 수, E: 간선의 수)
• 적용 분야
  • 최단 경로 찾기: 가중치가 동일한 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는데 사용된다.
  • 네트워크 탐색: 네트워크 구조에서 모든 노드(컴퓨터, 사용자 등)를 탐색하는데 유용하다.
  • AI와 게임 개발: AI의 길찾기 알고리즘이나 게임 캐릭터의 움직임을 제어하는데 사용된다.
  • 웹 크롤링: 웹 페이지를 너비 우선으로 탐색하면서 데이터를 수집하는데 사용된다. 

BFS 작동 방식 

1. 시작 정점을 큐에 넣는다. 
2. 큐가 비어있지 않는 동안:
   1. 큐에서 정점을 하나 꺼내어 방문한다.
   2. 방문한 정점에 인접한 모든 정점들을 큐에 넣는다. (단, 아직 방문하지 않은 정점들만)

BFS 구현 방법(JavaScript)

const bfs = (graph, start) => {
  const visited = new Set(); // 방문한 정점을 저장하는 집합
  let queue = [start]; // 탐색할 정점을 저장하는 큐
  const result = [];

  while (queue.length > 0) {
    let node = queue.shift(); // 큐에서 정점을 하나 꺼냄
    if (!visited.has(node)) {
      result.push(node);
      visited.add(node); // 방문한 정점을 집합에 추가

      // 큐에 인접한 정점을 추가 (아직 방문하지 않은 정점들만)
      for (let neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
  return result;
};

bfs(graph, start) // ['A', 'B', 'C', 'D', 'E', 'F']

 

탐욕적 탐색 (Greedy Search)

• 설명: 매 단계에서 가장 최적의 선택을 하는 방식으로 문제를 해결하는 탐색 알고리즘이다. 최적해를 보장하지는 않지만, 많은 경우에 근사해를 빠르게 찾을 수 있다.
• 적용 분야: 최소 신장 트리, 최단 경로 문제 등

 

휴리스틱 검색 (Heuristic Search)

• 설명: 휴리스틱 함수를 사용하여 문제 공간을 탐색하는 알고리즘이다. A* 알고리즘이 대표적인 예로, 휴리스틱 함수를 사용하여 최적의 경로를 찾는다.
• 적용 분야: 게임 인공지능, 경로 찾기 문제 등