[SEB FE] Section3 Daily Coding 08_treeBFS
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 너비 우선 탐색(BFS, Breadth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
입출력 예시
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]
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5, 7, 6]문제접근
예시에서 생성자 함수(Node)와 메소드(addChild)를 통해서 만든 root 객체를 출력한다면,아래와 같다.
{
value: 1,
children: [
{
value: 2,
children: [
{ value: 4, children: [] },
{ value: 5, children: [] },
],
},
{ value: 3, children: [] },
],
}이 root객체를 시작으로 너비 우선 탐색을 하면 1, 2, 3, 4, 5 의 순서로 탐색을 해야한다.
여기에 Node(6), Node(7)을 추가하면, 1, 2, 3, 4, 5, 7, 6 순서로 탐색해야 한다.
{
value: 1,
children: [
{
value: 2,
children: [
{ value: 4, children: [{ value: 6, children: [] }] },
{ value: 5, children: [] },
],
},
{ value: 3, children: [{ value: 7, children: [] }] },
],
}깊이 우선 탐색과 달리 너비 우선 탐색은 시작 노드에서 인접한 노드를 먼저 탐색하는 방법이라고 한다. dfs와는 달리 자식노드로 파고드는 재귀적인 방법으로 풀 수 없다. 일반적으로 큐를 이용해서 반복적 형태로 구현한다.
큐(queue)는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식
예시의 루트노드를 너비 우선 탐색하는 과정을 생각해보면,
1. (value:1)을 먼저 큐에 담고
- 현재 큐의 상태: [(value:1)]
2. (value:1)을 큐에서 꺼낸 뒤에 (value:1)의 인접한 자식노드인 (value:2), (value:3)를 큐에 담는다.
- 현재 큐의 상태: [(value:2), (value:3)]
3. 다시 큐의 맨 처음 요소인 (value:2)를 꺼내고 인접한 자식노드인 (value:4) (value:5)를 큐에 담는다.
- 현재 큐의 상태: [(value:3), (value:4), (value:5)]
4. 다시 큐의 맨 처음 요소인 (value:3)를 꺼내고 인접한 자식노드인 (value:7)을 큐에 담는다.
- 현재 큐의 상태: [(value:4), (value:5), (value:7)]
5. 다시 큐의 맨 처음 요소인 (value:4)를 꺼내고 인접한 자식노드 (value:6)을 큐에 담는다.
- 현재 큐의 상태: [(value:5), (value:7), (value:6)]
6. 다시 큐의 맨 처음 요소 (value:5)를 꺼내고, 인접한 자식 노드가 없으니까 큐에 새로운 노드를 넣는 과정은 생략한다.
- 현재 큐의 상태: [(value:7), (value:6)]
7. 큐의 맨 처음 요소 (value:7)을 꺼낸다.
- 현재 큐의 상태: [(value:6)]
8. 큐의 맨 처음 요소 (value:8)을 꺼낸다.
- 현재 큐의 상태: []
9. 큐에 저장된 노드가 없으니까 탐색을 종료한다.
요약하면,
큐에 첫번째 요소를 꺼내고, 해당 요소와 인접한 자식 노드를 큐에 담는 과정을 반복한다. 이 과정을 큐에 저장된 노드가 없을때까지 계속 반복한다.
수도코드
- 큐로 기능할 배열은 선언하고, 탐색할 노드를 배열에 담아준다.
- 탐색 순서를 저장할 빈 배열 order를 선언한다.
- 큐의 0번 인덱스를 변수 head로 저장하고 (큐 배열에서는 삭제)
- head의 value를 order배열에 저장한다.
- head의 children 배열의 요소를 큐에 저장한다.
- 위의 3-4-5 과정을 큐 배열의 길이가 0이 될때까지 반복한다.
- order 배열을 리턴한다.
작성한 코드
let bfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let queue = [node];
let order = [];
while(queue.length > 0) {
//큐에서 첫번째 요소를 제거하고, 이를 head에 저장한다.
const head = queue.shift()
// head value값을 order 배열에 저장한다.
order.push(head.value);
// head의 자식 노드를 하나씩 큐에 담아준다.
for(let child of head.children) {
queue.push(child)
}
}
return order;
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};레퍼런스 코드
let bfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let queue = [node];
const values = [];
while (queue.length > 0) {
const head = queue[0];
queue = queue.slice(1);
values.push(head.value);
head.children.forEach((child) => queue.push(child));
}
return values;
};shift()로 큐에서 삭제하는 것이 아니라 slice()로 head를 뺀 나머지 요소를 복사해서 큐에 재할당 해주었다.
참고
