너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS)

오늘은 바로 지난번에 풀었던 게임 맵 최단거리 문제 풀이에서 알고리즘으로 활용한 너비 우선 탐색(BFS)에 대해서 공부해보려 합니다. 먼저 너비 우선 탐색(BFS: Breadth First Search) 명칭의 의미를 확인해보겠습니다.

 

 

혹시 지난 게임 맵 최단거리 문제 풀이가 궁금하신 분은 아래에 있는 이전 포스팅을 보고 오시기 바랍니다.

 

 

2022.07.29 - [컴공생의 Knowledge/Algoritm Solution] - [프로그래머스] 깊이/너비 우선 탐색 - 게임 맵 최단거리 문제 풀이 (feat.JS)

[프로그래머스] 깊이/너비 우선 탐색 - 게임 맵 최단거리 문제 풀이 (feat.JS)

 

 

 

 

너비 우선 탐색 (BFS: Breadth First Search)

너비 우선 탐색(BFS)는 Breadth(폭)을 우선적으로 탐색하여 길을 찾아가는 알고리즘입니다. 여기서 폭이란 현재 위치에서 갈 수 있는 가장 가까운 거리를 의미하는 것입니다. 그럼 더 자세한 정의에 대해서 확인해보겠습니다.

 

 

 

 

∞ 너비 우선 탐색(BFS)의 정의

너비 우선 탐색은 Breadth First Search로 너비를 우선으로 탐색을 진행하는 알고리즘입니다.

즉, 현재 위치에서 갈 수 있는 가장 가까운 지점을 먼저 탐색하는 방법으로 시작지점으로부터 탐색지점이 넓게 퍼진다는 점이 특징입니다.

BFS 알고리즘은 두 지점 사이의 최단 거리 구할 때나 어떤 경로를 찾고자 할 때 많이 활용되는 알고리즘입니다.

 

 

아래는 간단하게 연결되어있는 여러 지점들 사이에서 A 지점을 시작으로 모든 지점을 탐색하는 길을 너비 우선 탐색(BFS)알고리즘을 통해 찾아본 길을 나타낸 것입니다. 

 

 

 

 

그럼 이 길을 어떤 방식으로 찾아내었는지 먼저 너비 우선 탐색의 특징부터 확인해보겠습니다.

 

 

 

 

∞ 너비 우선 탐색(BFS)의 특징

• Queue 자료구조를 활용하여 구현
  • 선 입[먼저 방문 노드를] 선 출[확인]의 구조로 인하여 Queue 자료구조를 활용한다.
• 길 찾기 알고리즘 중 최단 경로 찾기에 최적 알고리즘
• 노드 방문 여부에 대해서 반드시 체크 필요
  • 체크하지 않을 경우, 무한 루프에 빠질 수 있다.

 

 

 

 

∞ 너비 우선 탐색(BFS)의 탐색 과정

① A 시작 (Queue 삽입: A)	② A 노드 탐색 (Queue 제거) -> B 확인 (Queue 삽입: B)
③ C 확인 (Queue 삽입: C)	④ B 노드 탐색 (Queue 제거) -> D 확인 (Queue 삽입: D)
⑤ C 노드 탐색 (Queue 제거)	⑥ D 노드 탐색 (Queue 제거)
⑦ 탐색 순서 (A-B-C-D)

 

 

 

이 너비 우선 탐색(BFS) 알고리즘의 탐색 과정에 대해서 확인해보았습니다. 이 알고리즘이 어떻게 위와 같이 탐색하는지 알고리즘에 대해서 파헤쳐보겠습니다.

 

 

 

 

∞ 너비 우선 탐색(BFS)의 알고리즘 순서

1. 시작 노드를 방문한다.
   • 방문한 노드를 큐에 삽입한다.
   • 방문한 노드를 체크한다.
2. 시작 노드의 인접한 노드를 차례로 방문한다.
   • 인접한 노드들을 순서대로 큐에 삽입한다.
   • 방문한 인접한 노드들을 방문한 노드로 체크한다.
3. 큐에서 가장 먼저 방문한 노드를 꺼내 시작 노드로 한다
   (이 노드를 시작 노드로 하여 BFS를 다시 시작한다.)
4. 큐의 내용이 없을 때까지 반복한다.

 

 

위의 너비 우선 탐색 알고리즘을 통해 JavaScript로 직접 구현을 통해 동작을 알아보는 시간을 갖겠습니다.

 

 

 

 

∞ 너비 우선 탐색(BFS)의 구현(JavaScript)

다음은 위에서 너비 우선 탐색으로 탐색 과정으로 보여준 예시의 그래프 형태를 코드로 구현하여 너비 우선 탐색 알고리즘 코드를 작성해보았습니다.

 

 

const GRAPH = {
    A: ["B", "C"],
    B: ["A", "C", "D"],
    C: ["A", "B", "D"],
    D: ["B", "C"]
}

function bfs(startNode) {
    const Queue = [];
    const visitedNode = [];

    Queue.push(startNode);
    visitedNode.push(startNode);
    while(Queue.length > 0) {
        const curNode = Queue.shift();
        for(let nearNode of GRAPH[curNode]) {
            if(!visitedNode.includes(nearNode)) {
                Queue.push(nearNode);
                visitedNode.push(nearNode);
            }
        }
    }

    return visitedNode;
}

console.log(bfs('A'));    // ['A', 'B', 'C', 'D']

 

 

bfs() 함수를 통해 얻어진 결과가 위에서 얻은 탐색 경로와 일치하는 것을 볼 수 있습니다.

bfs() 함수를 구현할 때 가장 키 포인트는 Queue 알고리즘으로 먼저 탐색가능한 노드를 선착순으로 관리할 수 있기에 너비 우선 탐색 알고리즘을 구현함에 있어 가장 중요하다고 생각합니다.

 

 

그럼 오늘은 너비 우선 탐색(BFS)에 대해서 공부해봤습니다.

함께 공부해주셔서 감사합니다.