# 너비 우선 탐색(BFS)

## 1. 개요

너비 우선 탐색(BFS, Breadth-First Search)는 그래프 탐색에 사용하는 알고리즘이다. 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

***

## 2. 너비 우선 탐색이란?

너비 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법을 말한다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐삭해는 것이다.

![BFS](https://velog.velcdn.com/images%2Fsukong%2Fpost%2F103fbeed-3f70-4074-9a7d-76915a7764f2%2FBFS.png)

주로 **두 노드 사이의 최단 경로** 혹은 **임의의 경로를 찾고 싶을 때** 사용한다.

***

## 3. 너비 우선 탐색의 특징

1. 직관적이지 않은 면이 있다.
   * 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
2. 재귀적으로 동작하지 않는다.
3. 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
4. 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 선입선출 원칙으로 탐색한다.

***

## 4. BFS 구현하기

```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"],
};

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

  // 2) 첫 시작으론 매개변수로 받은 노드르 정하기
  needVisit.push(startNode);

  while (needVisit.length !== 0) {
    // 3) 매 반복문 마다 needVisit 배열의 맨 앞 요소를 꺼내 탐색하기
    const node = needVisit.shift();

    // 4) 이미 반문한 모드가 아니라면
    if (!visited.includes(node)) {
      // 5) 노드를 visited 배열의 마지막 요소로 추가하기
      visited.push(node);
      // 6) 노드와 연결된 노드들을 needVisit 배열에 추가하기
      needVisit = [...needVisit, ...graph[node]];
    }
  }
};
```

`BFS` 함수는 `graph`와 탐색을 시작할 노드인 `startNode`를 매개변수로 받는다.

***

### 1) 탐을 마친 노드들과 탐색을 해야 할 노드들을 저장하기

```javascript
let visited = [];
let needVisit = [];
```

너비 우선 탐색 알고리즘은 큐 자료구조를 사용한다. 위의 변수 중 `needVisit` 배열이 바로 큐 자료구조를 띄고있다. 단 여기서는 선입선출의 개념만 가져오고 있다. 정확히 구현하기 위해서는 시간 복잡도를 O(1)로 맞추어야 한다.

`needVisit` 배열은 앞으로 내가 탐색을 해야 할 노드들이 들어있는 배열이며 `visited` 배열은 탐색을 마친 노드들이 들어있다.

***

### 2) 첫 시작으론 매개변수로 받은 노드르 정하기

```javascript
needVisit.push(startNode);
```

처음으로 탐색을 할 노드는 당연히 매개변수로 받은 노드이다. 그렇기 때문에 `needVisit` 배열에 `startNode`를 추가한다. 이때 `needVisit` 배열엔 `startNode` 만 들어있다.

***

### 3) 매 반복문 마다 needVisit 배열의 맨 앞 요소를 꺼내 탐색하기

```javascript
const node = needVisit.shift();
```

반복문이 실행 될 때 마다 `needVisit` 배열의 `0`번째 요소를 가져온다. 해당 요소가 이번 차례에 탐색을 진행할 노드이다.

***

### 4) 이미 반문한 모드가 아니라면

```javascript
if (!visited.includes(node)) {
}
```

이미 `visited` 배열에 탐색할 노드가 있다면 탐색이 중복되므로 이와 같은 경우엔 탐색을 진행하지 않고 다음 반복문으로 넘어간다. 하지만 `visited` 배열에 노드가 없다면 탐색할 노드이기 때문에 `if`문이 실행된다.

***

### 5) 노드를 visited 배열의 마지막 요소로 추가하기

```javascript
visited.push(node);
```

`if`문에서 탐색할 노드를 탐색을 마친 배열인 `visited` 배열에 추가한다. 이로써 다음번엔 다시 탐색을 하지 않아도 된다.

***

### 6) 노드와 연결된 노드들을 needVisit 배열에 추가하기

```javascript
needVisit = [...needVisit, ...graph[node]];
```

탐색을 헤야 할 노드들이 들어있는 `needVisit` 배열에 현재 탐색하고 노드와 연결된 노드들을 추가한다. 이때 배열의 마지막에 추가해야 한다. 이 말은 즉, 앞의 노드들을 탐색을 먼저 끝내야 현재 탐색하고 있는 노드와 연결된 노드들을 탐색할 수 있다는 것이다.

***

## 5. Conclusion

> 아직 BFS(너비 우선 탐색)를 언제 활용을 해야할 지 감이 잘 잡히지 않는다. 뿐 만 아니라 BFS로 문제를 풀어야 한다는 것을 알았어도 문제의 조건에 맞게 그래프를 구현하고 그 그래프를 이용해서 너비 우선 탐색을 구현하는 것은 상상이 잘 되지 않는다. 아직 문제를 깊이 풀어보지 않아서 그런 것 같다. 많은 문제가 역시나 답인 것 같다. 프로그래머스에서 기초를 얼른 다지고 리트코드에서 더 많은, 다양한 문제를 풀어보고 싶다.

***

## 참고

[\[알고리즘\] 너비 우선 탐색(BFS)이란](https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html)\
[자바스크립트로 구현하는 너비우선탐색(BFS) 깊이우선탐색(DFS)](https://ryusm.tistory.com/48)

***

📅 2022-09-30


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://noah-dev.gitbook.io/til/data-structure-and-algorithm/algorithm/bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.