BFS(Breadth-first search)
지난번엔 DFS문제를 만나 가볍게 다뤄본 적이 있는데
이렇게나 빨리 BFS를 만났다.
BFS는 너비 우선 탐색으로 그래프 탐색 알고리즘 중 하나입니다. 시작 정점으로부터 거리가 가까운 정점부터 탐색해 나가는 방식으로, 레벨 순서대로 탐색하는 방법입니다.
BFS는 큐 자료구조를 이용하여 구현할 수 있습니다. 시작 정점을 큐에 넣고, 해당 정점과 인접한 정점을 모두 큐에 넣어 탐색합니다. 그러고 나서 큐에서 하나씩 정점을 꺼내면서 그 정점과 인접한 정점을 다시 큐에 넣어 탐색을 진행합니다. 이 과정을 큐가 비어질 때까지 반복합니다.
최단 경로를 찾는 문제에서 많이 사용되며, 그래프의 정점들이 거리에 대한 정보를 가지고 있을 때 유용합니다.
ex) 길찾기, 네트워크 최적 경로, 게임 맵 최단거리, 퍼즐, 탐사(로봇, 드론 경로)
오늘도 문제를 보면서 자세히 살펴보도록 하겠다
🏋🏽문제
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 너비 우선 탐색을 합니다.
이때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
🔍풀이
let bfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let result = [];
let queue = [node]
while(queue.length >0){
let current = queue.shift();
result.push(current.value);
for(let i=0; i<current.children.length; i++){
queue.push(current.children[i]);
}
}
return result;
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};✅ 입출력 예시
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5]🗝️ 이제 코드를 하나씩 살펴보자
let Node = function (value) {
this.value = value;
this.children = [];
};1. Node 함수를 정의한다.
이 Node 함수는 인자로 value를 받아 노드를 생성한다. value는 노드의 value의 값이며 children 배열은 자식 노드들의 배열이다.
Node 함수의 인자로 들어간 1이 value가 되는것을 볼 수 있다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};2. Node 함수의 prototype객체에 addChild 함수를 정의한다.
인자로 자식 노드를 받아 현재 노드의 children 배열
에 추가한다. 반환값은 추가된 자식 노드이다.
입출력예시의 두 번째 줄을 실행시켜 보자
new Node(1)로 생성된 객체의 children 값에 new Node(2)라는 객체가 들어온 것을 확인할 수 있다.
그러니까 지금 root객체의 상태는
root = {
value:1,
children:[{value:2, children[]}],
}이렇게 객체가 중첩된 모양이다.
다시 한번 입출력 예시를 보면
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5]이런 모양인데 이것을 객체형태로 표현하자면..
지난번엔 이 부분을 훑고 지나가지 않아서 한번 다뤄봤다.
본격적으로 bfs 구현을 살펴보자면
결국 중첩된 객체의 값을 단계별로 탐색하는 것이다.
따라서 bfs 함수는 이렇게 구현할 수 있다.
let result = [];
let queue = [node];result 배열에는 방문한 노드의 값을 저장할 것이고
queue는 시작 node 객체를 배열에 넣어준다.
while(queue.length >0){
let current = queue.shift();
result.push(current.value);
for(let i=0; i<current.children.length; i++){
queue.push(current.children[i]);
}
}while(node배열의 요소가 모두 사라질 때까지)
아래를 반복한다.
1. current 변수에 현재 노드의 첫 번째 요소를 shift() 메서드를 통해 저장한다.
2. result 배열에 1번에서 가져온 객체요소의 값을 push 한다.
해당 요소의 children 값인 배열의 길이만큼 반복문을 돌면서
queue 배열에 현재 1번의 children노드들의 값을 push 한다.
{value: 1, children: Array(2)}결국 queue에 value와 children값을 가진 객체를 계속 push하면서
value값을 가져오는것!
마무리
사실 bfs와 dfs에 대해 자세한 구현사항이 있지만 아직 이해할정도가 못되어서 다루지 못했다 🥹 이 포스팅은 코플릿 문제에 한정되어있고 프로그래머스 문제를 다뤄보면서 더 자세히...알아보기로..