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);
};