TIL 240715 - BFS / DFS

데이터는 선형 구조(배열, 링크드 리스트, 스택, 큐 등)와 비선형 구조(트리, 그래프)로 이루어져 있다.

여기서 탐색이 어려운 비선형 구조를 탐색할 수 있는 두가지 대표적인 알고리즘이 BFS, DFS이다.

1. DFS (깊이 우선 탐색)

1) DFS란?

루트 노드(혹은 임의의 한 노드)에서 시작해서, 해당 분기를 모두 탐색한 뒤 다음 분기를 탐색하는 방법이다.

말로 설명하면 뭔소린지 이해가 안될텐데, 그림으로 보면 바로 이해된다. 

이렇게 한 분기에서 막다른길이 나올때까지 모두 탐색한 후 다른 분기로 이동하는 것.. 이 때 중복 탐색을 방지하기 위해 이미 탐색을 완료한 곳은 표시를 해야 한다.

 

2) DFS 특징

자기 자신을 호출하는 순환 알고리즘의 형태를 띈다. (재귀함수 이용)

• 시작점 설정 (1번에서 시작)
• 시작점에서 방문하지 않은 정점으로 이동 (2번으로 이동)
• 해당 노드에서 방문하지 않은 정점으로 이동 (3, 4번으로 이동..) > 반복..
• 이동할 정점이 없을 경우(4번에서 더이상 이동할 노드 x) > 상위 정점으로 돌아가 방문하지 않은 정점으로 이동(5번으로 이동) > 반복.. (6번, 7번 이동 > 8번 이동...)

3) DFS의 장단점

• 장점 : 코드가 직관적이고 구현하기 쉽다
• 단점 : 깊이가 깊어지면 스택 메모리가 지나치게 커지며, 최단 경로를 알기 어렵다.

4) 스택을 이용한 DFS 코드

function dfs(graph, start, visited) {
  const stack = [];
  stack.push(start);

  while (stack.length) {
    let v = stack.pop();
    if (!visited[v]) {
      console.log(v);
      visited[v] = true;

      for (let node of graph[v]) {
        if (!visited[node]) {
          stack.push(node);
        }
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 4 3 2 5 1

 

5) 재귀함수를 활용한 DFS 코드

const dfs = (graph, v, visited) => {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);

  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
    if (!visited[node]) {
      dfs(graph, node, visited);
    }
  }
}

const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 1 5 2 4 3

 

 

2. BFS (너비 우선 탐색)

1) BFS란?

시작점에서 가까운 정점부터 순서대로 탐색하는 알고리즘이다.

DFS랑은 다르게, 한 분기의 끝까지 가지 않고, 여러 분기들을 얕게 거쳐가며 조회하는 방식이다.

2) BFS 특징

출발점을 먼저 큐에 넣고, 큐가 빌때까지 다음을 반복한다.

• 큐에 저장된 정점을 하나 Deque 한다.
• 뺀 정점과 연결된 모든 정점을 큐에 넣는다.

그러니까.. 

• 큐에 시작 정점(1번)을 넣는다.
• 큐의 가장 앞에 있는 값(1번)을 뽑는다. 해당 정점과 연결된 정점(2, 3, 4번)을 가져와 큐에 집어넣는다.
• 큐의 가장 앞에 있는 값(2번)을 뽑고, 해당 정점과 연결된 정점(5번)을 가져와 큐에 집어넣는다.

...를 반복한다.

 

3) BFS 장단점

• 장점 : 시간/공간 복잡도 면에서 안정적이며, 최단 경로를 구할 수 있다.
• 단점 : 구현 방법이 비교적 까다롭고, 모든 지점을 탐색한다는 가정 하에 메모리가 어느정도 준비되어 있어야 한다.

4) BFS 코드

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

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
    if (!visited.includes(node)) { // 해당 노드 방문이 처음이라면,
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};