[js100제] 73번 - 최단경로

1. 최단거리문제

dfs /bfs의 약간 응용같아 보였다.

• 출발/도착이 있다.
• 나는 BFS방식이라고 생각하고 풀었다.

2. 첫 실패다

let graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B", "G"],
  E: ["B", "F"],
  F: ["C", "E", "H"]
};
function shortCut(graph, start, end) {
  let answer = [];
  let path = [];
  let queue = [];
  path.push(start);
  answer.push(start);
  queue.push(start);
  while (queue.length !== 0) {
    let n = queue.shift();
    if (!path.includes(graph[n])) {
      if (graph[n].includes(end)) {
        answer.push(n, end);
        break;
      }
      queue.push(...graph[n]);
      path.push(...graph[n])
    }
  }
  return answer.length - 1;
}

console.log(shortCut(graph, "A", "H"));

• 문제에서 준대로는 할 수 있다. (A->C)는 찾을 수 있다.
• 그러나 graph를 확장했더니 안된다.
• 처음과 마지막 경로는 얻는데 중간경로를 얻지 못함
• 게다가 경로를 지나간 횟수도 얻을 수 없다.

3. 정답코드

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

const start = "A";
const end = "G";

let queue = [start];
let visited = [start];

function solution() {
  let count = -1;

  while (queue.length !== 0) {
    count += 1;

    let size = queue.length;

    for (let i = 0; i < size; i++) {
      let node = queue.splice(0, 1);
      console.log(count,node[0],end);
      if (node[0] === end) {
        return count;
      }
      for (let next_node in graph[node]) {
        if (!visited.includes(graph[node][next_node])) {
          visited.push(graph[node][next_node]);
          queue.push(graph[node][next_node]);
        }
      }
    }
  }
}
let answer = solution();

• 역시..다르다
• 제대로 구현된 너비탐색스타일 같다.
• 층층 내려갈 때마다 카운트를 올리는 방식.
• 핵심은 while 과 for
• while은 너비 하나를 탐색할 때다 (count+1)
• for 루프를 한번 돌면서 이전 queue를 다 지우고
  다음 nodes들을 받아온다. (반복)

3. 공부후 내가 다시 작성한 코드

(쩔수없이 매우 유사..)

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

function shortCut(start,end){

  let queue=[start];
  let visited=[start];
  let count = -1;
  while( queue.length !== 0  ){
    count += 1;
    let lengthOfQ = queue.length;
    for (let i=0; i<lengthOfQ; i++){
      let n = queue.shift();
      if(n === end){ return count }
      for( let next in graph[n] ){
        if(!visited.includes(next)){
          queue.push(graph[n][next]);
          visited.push(graph[n][next]);
        }
      }
    }
    
  }

}

console.log(shortCut("A","H"));