자주 사용하게 되는 알고리즘에 대해서 하나씩 알아보겠습니다.

그래프 탐색 알고리즘

BFS와 DFS는 그래프 탐색 알고리즘 중 가장 기본적이고 중요한 알고리즘입니다.
그렇다면 그래프 탐색 알고리즘은 정확히 어떤 알고리즘일까요?
그래프 탐색에 관해서 설명하기 전에, 그래프의 기본적인 개념부터 알아보겠습니다.

그래프(graph)란?

그래프는 객체들 간의 이진 관계를 모델링하는데 사용되는 수학적인 구조입니다.
그래프는 노드(Node) 또는 정점(Vertex) 그리고 이러한 노드/정점들을 연결하는 간선(Edge) 으로 구성됩니다.

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

BFS는 시작 정점에서 가까운 정점부터 차례대로 그래프의 모든 정점들을 탐색합니다.

특징

• 큐(Queue)를 사용하여 구현합니다.
• 두 노드 사이의 최단 경로나 장애물의 최소 이동 횟수 등을 찾을 때 사용됩니다.

동작 과정

• 시작 정점을 큐에 삽입하고 방문 처리합니다.
• 큐에서 정점을 꺼내 해당 정점의 인접 정점 중 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리합니다.
• 2의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

예시 코드

function BFS(graph, start) {
  let visited = {};
  let queue = [start];

  while (queue.length) {
    let node = queue.shift();
    if (!visited[node]) {
      console.log(node);
      visited[node] = true;
      queue.push(...graph[node]);
    }
  }
}

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

DFS는 시작 정점에서 멀리 떨어져 있는 정점을 우선적으로 탐색합니다.

특징

• 스택(Stack) 또는 재귀를 사용하여 구현합니다.
• 모든 노드를 방문하고자 할 때 사용됩니다.

동작 과정

• 시작 정점을 스택에 넣고 방문 처리합니다.
• 스택의 최상단 정점에서 방문하지 않은 인접 정점이 있으면 그 인접 정점을 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 정점이 없으면 스택에서 최상단 정점을 꺼냅니다.
• 2의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

예시 코드

function DFS(graph, node, visited = {}) {
  if (node in visited) return;

  console.log(node);
  visited[node] = true;
  for (let neighbor of graph[node]) {
    DFS(graph, neighbor, visited);
  }
}

결론

BFS, DFS 둘 다 그래프의 모든 노드를 방문한다는 점에서는 동일하지만, 탐색의 순서와 방식에서 차이가 있습니다. 문제의 요구 사항과 그래프의 특성에 따라 적절한 탐색 알고리즘을 선택해야 합니다.