알고리즘 2. BFS(너비 우선 탐색)

시작 정점에서 인접한 정점을 먼저 탐색하는 너비 우선 탐색을 통해 가중치가 없는 그래프에서 두 정점 사이의 최단 경로를 구하기

1. 너비 우선 탐색(BFS)이란?

① 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법이다.

② [완전 탐색]을 수행하기 위해 사용할 수 있는 방법 중 하나다.

③ (모든 간선의 길이가 동일할 때) 최단 거리를 탐색하기 위한 목적으로 사용할 수 있다.

④ 큐(queue) 자료구조를 사용한다.

👉 기본적으로 DFS는 스택, BFS는 큐를 사용한다.

 

 

2. 너비 우선 탐색(BFS) 기본 동작 방식

1) 시작 노드를 큐에 넣고 [방문 처리]한다.
2) 큐에서 아무 노드가 없을 때까지: 
  a. 큐 가장 앞 노드를 꺼낸다.
  b. 꺼낸 노드에 인접한 노드들을 모두 보면서:
    ㄱ) 처음 방문한 노드면:
       ⅰ. 방문한 노드 [방문 처리]한다.
       ⅱ. 큐에 넣어준다.

 

 

3. 너비 우선 탐색(BFS)과 최단 경로

① BFS는 간선의 비용이 동일할 때 [최단 거리] 문제를 해결하기 위해 사용 가능하다.
② BFS는 다익스트라 최단 경로 알고리즘과 유사한 특징이 있다.

👉 다익스트라는 간선의 비용이 서로 다를 수 있을 때 사용 가능하다.
1) 다익스트라 알고리즘은 일반 큐 대신에 우선순위 큐를 사용한다.
2) 다익스트라는 특정 노드에 대하여 [최단 거리] 값이 갱신될 수 있다. (더 짧은 경로를 찾는 경우)

 

 

4. 너비 우선 탐색(BFS) 소스 코드 예시

// BFS 메서드 정의
function bfs(graph, start, visited) {
  const queue = new Queue();
  queue.enqueue(start);
  // 현재 노드를 방문 처리
  visited[start] = true;
  // 큐가 빌 때까지 반복
  while (queue.getLength() != 0) {
    // 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.dequeue();
    console.log(v);
    // 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for (const i of graph[v]) {
      if (!visited[i]) {
        queue.enqueue(i);
        visited[i] = true;
      }
    }
  }
}

// 각 노드가 연결된 정보를 표현
graph = [
    [],
    [2, 3, 4],
    [1],
    [1, 5, 6],
    [1, 7],
    [3, 8],
    [3],
    [4],
    [5]
];

// 각 노드가 방문된 정보를 표현
visited = Array(9).fill(false);

// 정의된 BFS 함수 호출
bfs(graph, 1, visited);

 

 

5. 온라인 저지 문제 풀이

2024.07.18 - [JS 코딩테스트/문제풀이] - [자바스크립트] 2606 바이러스

2024.07.19 - [JS 코딩테스트/문제풀이] - [자바스크립트] 1697 숨박꼭질

2024.07.20 - [JS 코딩테스트/문제풀이] - [자바스크립트] 24444 알고리즘 수업 - 너비 우선 탐색 1

2024.07.22 - [JS 코딩테스트/문제풀이] - [자바스크립트] 2178 미로 탐색

2024.07.24 - [JS 코딩테스트/문제풀이] - [자바스크립트] 18352 특정 거리의 도시 찾기

2024.08.05 - [JS 코딩테스트/문제풀이] - [자바스크립트] 게임 맵 최단거리

 

 

 

✔ 참고

나동빈, "JavaScript로 끝내는 자료구조/알고리즘 (코딩 테스트)", [패스트캠퍼스]