[알고리즘] DFS, BFS 탐색 알고리즘 (Feat. JavaScript로 구현하기)

탐색 알고리즘이란?

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘입니다.

 

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

시작점부터 갈 수 있는 정점까지 깊이있게 파고 드는 탐색 알고리즘

DFS 장단점

장점
1. 직관적인 코드, 구현이 용이

단점
1. 깊이가 깊어질수록 예측하기 어려운 메모리 비용
2. 최단 경로 파악 불가

 

DFS의 원리

*스택 (LIFO)
push() : 배열 끝에 새로운 요소 추가 및 새로운 길이 반환
pop(): 배열의 마지막 요소 제거 및 그 요소 반환

A B D E F C G H I J 순으로 깊이를 기준으로 먼저 탐색하는 알고리즘입니다.
위 그림을 기준으로 DFS의 원리를 확인해보도록 하겠습니다.

(1) A를 시작 정점으로, 스택에 A를 넣습니다. (스택 : A)
(2) A를 뽑으며, 이와 연결된 정점 B, C를 스택에 넣습니다. (스택 : B, C)
(3) 스택의 가장 위에 있는 B를 뽑고, B와 연결된 D를 스택에 넣습니다. (스택 : C, D)
(4) 스택의 가장 위에 있는 D를 뽑고, D와 연결된 E, F를 스택에 넣습니다. (스택 : C, E, F)
(5) 스택의 가장 위에 있는 F를 뽑습니다. F와 연결된 노드는 없으므로, 더 이상 추가하지 않습니다. (스택 : C, E)
...
→ 이와 같이 스택을 통해 깊이 우선으로 탐색할 수 있습니다.
한 노드를 기준으로 가능한 깊이를 우선적으로 탐색하며,
더 이상 방문할 노드가 없다면 이전 노드로 돌아가 다음 노드를 탐색합니다.

이렇게 스택의 최상단 노드에서 탐색을 계속하다가
더 이상 방문할 노드가 없을 때 이전 단계로 돌아가는 것이 DFS의 특징입니다.

 

JavaScript의 DFS 적용

상단의 그래프를 코드로 나타내면 아래와 같습니다.

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']
};

function DFS(graph, startNode) {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야 할 노드들

  needVisit.push(startNode); // 시작 노드 needVisit에 추가
  
  // needVisit 배열이 빌 때까지 (모든 노드를 탐색할 때까지) 반복
  while (needVisit.length !== 0) { 
    // needVisit 배열의 마지막 요소를 제거하고 그 요소를 node에 저장
    const node = needVisit.pop();
    
    // visited 배열에 node가 없다면 (노드를 아직 방문하지 않았다면)
    if (!visited.includes(node)) {
      // visited 배열에 node를 추가
      visited.push(node);

      // needVisit 배열 끝에 현재 노드의 인접 노드들을 추가
      needVisit = [...needVisit, ...graph[node].reverse()];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

 

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

시작점부터 가까운 정점부터 순서대로 방문하는 탐색 알고리즘

BFS 장단점

장점
1. 비효적으로 효율적인 운영이 가능하며, 시간/공간 복잡도 면에서 안정적
2. 최단 경로 파악 가능

단점
1. 비교적 구현이 까다로우며, 모든 지점을 탐색한다는 가정 하에 큐의 메모리가 준비되어야 합니다.

 

BFS의 원리

*큐 (FIFO)
push() : 배열 끝에 새로운 요소 추가 및 새로운 길이 반환
shift() : 배열의 첫 번째 요소를 제거하고, 그 요소를 반환

A B C D G H I E F J 순으로 너비를 기준으로 먼저 탐색하는 알고리즘입니다.
위 그림을 기준으로 BFS의 원리를 확인해보도록 하겠습니다.

(1) A를 시작 정점으로, 큐에 A를 넣습니다. (큐 : A)
(2) A를 뽑으며, 이와 연결된 정점 B, C를 큐에 넣습니다. (큐 : B, C)
(3) 큐의 가장 앞에 있는 B를 뽑고, B와 연결된 D를 큐에 넣습니다. (큐 : C, D)
(4) 큐의 가장 앞에 있는 C를 뽑고, C와 연결된 G, H, I를 큐에 넣습니다. (큐 : D, G, H, I)
(5) 큐의 가장 앞에 있는 D를 뽑고, D와 연결된 E, F를 큐에 넣습니다. (큐 : G, H, I, E, F)
...
→ 이와 같이 큐를 통해 단계별로 탐색할 수 있습니다.

 

JavaScript의 BFS 적용

상단의 그래프를 코드로 나타내면 아래와 같습니다.

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']
};


const BFS = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야 할 노드들

  needVisit.push(startNode); // 시작 노드 needVisit에 추가

  // needVisit 배열이 빌 때까지 (모든 노드를 탐색할 때까지) 반복
  while (needVisit.length !== 0) {
    // needVisit 배열의 첫 번째 요소를 제거하고 그 요소를 node에 저장
    const node = needVisit.shift();
    
    // visited 배열에 node가 없다면 (해당 노드를 아직 방문하지 않았다면)
    if (!visited.includes(node)) {
      // visited 배열에 node를 추가
      visited.push(node);
      
      // needVisit 배열 뒤에 현재 노드의 인접 노드들을 추가
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(BFS(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

 

✨ 정리

그럼 DFS, BFS 언제 사용해야 되는걸까요?

DFS는 스택이나 재귀를 이용해 깊이를 우선으로 탐색하는 알고리즘이기 때문에,
모든 노드를 방문해야 하는 경우에 사용하기 좋습니다.

또한, 경로의 깊이가 해답에 영향을 미치는 문제나
특정 노드에서 시작해 모든 노드를 방문하는 경로를 찾는 문제 등에 유용합니다.

 

BFS는 큐를 이용해 너비를 우선으로 탐색하는 알고리즘이기 때문에,
최단 경로를 찾는 문제에 주로 사용됩니다.

또한, 두 노드 사이의 최단 경로나 가까운 노드를 먼저 방문하는 문제 등에 적합합니다.

 

아직 저에게도 그래프 문제가 어렵게 느껴지지만, 조금씩 이해하고 응용하다 보면 점점 익숙해질 거라고 생각합니다.

계속해서 도전하고 학습합시다 🔥