[js100제] 문제72 너비우선정렬

너비우선정렬,
오밤중에 하다보니 제정신이 아니라 문제적코드를 작성했다.

1.문제적코드(?)

• 목표: stack배열에 너비우선으로 순서대로 넣는다.
• E(start)를 기준으로 D와 A를 for문으로 돌린다.
• D로 가서-> stack에 없는 F를 queue로 올린다.
  stack = ["E"]
  queue = ["D","A","F"];
• A로 간서-> stack에 없는 C,B를 queue로 올린다.
  queue = ["D","A","F","C","B"];
• 이후 queue를 차례대로 stack으로 올린다.
  stack = ["E","D","A","F","C","B"].

문제점은, E를 기준으로 value 배열의 길이가 2개인지라,
그 두개에 대해서만 실행이 되며, F,C,B에 더 많은 그래프가 생겨나면 쓸 수 없는 코드다. 다시만들어야겠다.

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

let stack = [];
let queue = [];
function wideSearch(graph, start) {
  stack.push(start);
  for (let i = 0; i < graph[start].length; i++) {
    queue.push(graph[start][i]);
  }
  let tempLen = queue.length;
  for (let i = 0; i < tempLen; i++) {
    graph[queue[i]].forEach(e => (!stack.includes(e) ? queue.push(e) : null));
  }
  for (let i of queue) {
    stack.push(i);
  }
  return stack;
}

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

2. 다시만든코드!

• 재귀를 써볼까 햇으나, 너비우선탐색 특성상 재귀로 구현은 어려워서 일단 보류.
• graph가 늘어나도 되는지 보기위해 이것저것 추가했다.
• 다행히 잘 되는데,
• while 안에 foreach에서 No-Loop-Func 경고가 뜬다.

let graph = {
  E: ["D", "A"],
  F: ["D", "H"],
  A: ["E", "C", "B"],
  B: ["A", "N"],
  C: ["A", "I"],
  D: ["E", "F", "G"],
  N: ["O"],
  H: ["L"]
};

let stack = [];
let queue = [];
function wideSearch(graph, start) {
  stack.push(start);
  queue = graph[start];
  while (queue.length > 0) {
    if(graph[queue[0]]){
      graph[queue[0]].forEach(e => (!stack.includes(e) ? queue.push(e) : null));
    }
    stack.push(queue.shift());
  }
}
wideSearch(graph, "E");
console.log(stack)

• no loop func 때문에 while부분을 조금 수정했다.
• 약간 3항연산자 / 메소드 을 더 쓰고싶은 마음이 있지만 왜인지는 모른다 그냥 for문은 투박해 보여서..
• 어쨋든 for로 바꾸니 경고는 없다!

while (queue.length > 0) {
    if(graph[queue[0]]){
      for(let i of graph[queue[0]]){
        if(!stack.includes(i)){
          queue.push(i)
        }
      }
    }

3.정답코드

• 정답코드는 graph추가는 불가하다.
• 하지만 역시 깔꿈하다..
• 시작을 queue에 넣고
• while
• 첫번째 요소를 n으로 & q에서 삭제
• if 를 통해 요소가 visited에 있으면 pass
• 없으면 visited에 넣고
• n의 하위요소(graph)에서 새로운 요소들만 sub으로 지정
• sub 요소들을 queue에 push.

정말 깔꿈하다

const graph = {
  'A': ['E', 'C', 'B'],
  'B': ['A'],
  'C': ['A'],
  'D': ['E','F'],
  'E': ['D', 'A'],
  'F': ['D'],
};

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

  while (queue.length !== 0){
    let n = queue.shift();
    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(bfs(graph, 'E'));```