[Javascript 코테 대비] 너비 우선 탐색: BFS

BFS: Breadth-First Search

너비 우선 탐색이라고도 부르며, 루트 노트에서 시작해서 인접한 노드들을 먼저 탐색하는 방법이다.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const BFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(BFS(graph, "A"));

실제 문제 풀이 시

BFS로 경우의 수 탐색하여, 몇 번 시행 후 목표가 될 수 있는지 알아내기

/**
* @param current: 현재 상태
* @param goal: 목표 상태
* 횟수: 
*/
function bfs(start, goal, size) { // current, goal
	const memory = {};
  	memory[start] = 0;
      
  	const queue = [];
  	queue.push(start);
  	
  	while(queue.length > 0) {
    	const visit = queue.shift();
      	const count = memory[visit];
      
      	if(visit === goal) return count;
      
      	for (const state of cases) { // 현재 가능한 경우의 수 탐색
        	if (memory[state] != undefined) continue;
          	memory[state] = count + 1;
          	queue.push(state);
        }
    }
  	return -1; // 탐색 실패
}