문제 72. 너비 우선 탐색

 

 

 

 

"너비우선탐색" 이란?

• 어떤 노드를 방문하여 확인한 후, 목표한 노드가 아니면 그 노드와 연결된 정점들 중에서 우선순위가 동일한 다른 노드를 찾고 그 순위에 없으면 그 다음 순위노드를 차례대로 찾는 방법이다.(깊이우선탐색의 연장선)

 

 

 

// 데이터
graph = {
    E: ["D", "A"],
    F: ["D"],
    A: ["E", "C", "B"],
    B: ["A"],
    C: ["A"],
    D: ["E", "F"],
  };


// 출력
E D A F C B

 

 

미리 생각해 봐야할 것

• 순서, 객체접근방식(키값, 벨류값 추출방식)

 

답

let graph = {
  E: ["D", "A"],
  F: ["D"],
  A: ["E", "C", "B"],
  B: ["A"],
  C: ["A"],
  D: ["E", "F"],
};

function dfs(graph, start) {
  let visited = [];
  let queue = [start];

  while (queue.length != 0) {
    let n = queue.shift(); // queue 의 맨 앞의 요소만 추출함(깊이 탐색과 유일하게 다른 부분)
    //   console.log(n)
    if (!visited.includes(n)) {
      visited.push(n);
      let sub = graph[n].filter((x) => !visited.includes(x));
      for (let i of sub) {
        queue.push(i);
      }
    }
  }
  return visited;
}

console.log(dfs(graph, "E"));