[BFS]이진트리 넓이 우선탐색

[BFS]이진트리 넓이 우선탐색

문제

https://choi95.tistory.com/110?category=854389

이전 깊이 우선 탐색한 이진트리를 이번에는 넓이 우선탐색으로 구현해보고자 한다.

문제풀이

너비 우선 탐색(BFS_Breadth-First Search)

루트 노드(Root Node) 또는 다른 임의의 노드를 정점으로, 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

적용 예: 두 노드 사이의 최단 경로 , 임의의 경로를 찾고 싶은 경우

방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용

최단 경로 탐색 이진 트리

문제풀이

function solution() { let answer = ""; let queue = []; queue.push(1); while(queue.length) { let v = queue.shift(); answer+=v + " "; for(let nv of [v * 2, v * 2 + 1]) { if(nv > 7) continue; queue.push(nv); } } return answer; } console.log(solution());

from http://choi95.tistory.com/129 by ccl(A) rewrite - 2021-08-13 20:00:17