IF - BFS
문제
아래와 같은 그래프를 넓이우선탐색 해보세요.
예시
Output : 1234567
풀이 및 회고
- 넓이우선탐색 (BFS) 는 기본적으로 큐 자료구조를 기반으로 한다.
- 큐 배열의 각 원소의 인덱스를 그래프의 깊이라고 가정한다.
- 큐 배열이 바닥날 때까지
while
문을 돌면서 큐에서 원소를 하나씩 뺀다. - 그래프 깊이를 하나 더 들어간 뒤, 해당 깊이에서의 원소들을 다시 큐에 push한다.
- 정리하면, 현재 깊이에서의 노드들에게 자식이 있는 경우, 앞쪽 노드부터 각자의 자식들을 모두 큐에 push 해놓는 식이다.
코드
const solution = () => {
let answer = "";
const queue = [];
queue.push(1);
while (queue.length) {
const v = queue.shift();
answer += v + "";
for (let nv of [v * 2, v * 2 + 1]) {
if (nv > 7) continue;
queue.push(nv);
}
}
console.log(answer);
};
Author And Source
이 문제에 관하여(IF - BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goody/IF-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)