너비 우선 탐색(BFS)

1. 개요

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

---

2. 너비 우선 탐색이란?

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

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

BFS

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

---

3. 너비 우선 탐색의 특징

1. 직관적이지 않은 면이 있다.

   • 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.

2. 재귀적으로 동작하지 않는다.

3. 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.

4. 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 선입선출 원칙으로 탐색한다.

---

4. 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) => {
  // 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) 탐을 마친 노드들과 탐색을 해야 할 노드들을 저장하기

let visited = [];
let needVisit = [];

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

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

---

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

needVisit.push(startNode);

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

---

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

const node = needVisit.shift();

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

---

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

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

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

---

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

visited.push(node);

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

---

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

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

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

---

5. Conclusion

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

---

참고

[알고리즘] 너비 우선 탐색(BFS)이란 자바스크립트로 구현하는 너비우선탐색(BFS) 깊이우선탐색(DFS)

---

📅 2022-09-30