문제 73. 최단 경로 찾기

입력받은 두정점이 공백으로 구분되어 주어질때,

두 정점 사이를 이동할 수 있는 최단 거리를 출력하는 프로그램을 작성하여라.

• 이때 최단 거리란, 정점의 중복없이 한 정점에서 다른 정점까지 갈 수 있는 가장 적은 간선의 수를 의미

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

// 입력
A F

// 출력
2

 

 

미리 생각해 봐야할 것

• 너비우선 탐색을 이용한다
• 그림을 그려보며 어떠한 방식으로 추척(?)할 것인가 생각한다.

 

 

답

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

function 최단경로(graph, start, end) {
  let count = -1;
  let 거쳐감 = [start];
  let 최종 = [start];

  while (거쳐감.length !== 0) {
    count += 1;
    let s = 거쳐감.length;
    for (let i = 0; i < s; i++) {
      let n = 거쳐감.splice(0, 1);
      if (n == end) {
        return count;
      }
      for (let j in graph[n]) {
        if (!최종.includes(graph[n][j])) {
          최종.push(graph[n][j]);
          거쳐감.push(graph[n][j]);
        }
      }
    }
  }
}

// let 입력 = prompt('입력쓰').split(' ');
let 입력 = ["A", "F"];
let start = 입력[0];
let end = 입력[1];

console.log(최단경로(graph, start, end));