문제 74. 최장 경로 찾기

 

 

 

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

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

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

// 데이터
graph = {
  1: [2, 3, 4],
  2: [1, 3, 4, 5, 6],
  3: [1, 2, 7],
  4: [1, 2, 5, 6],
  5: [2, 4, 6, 7],
  6: [2, 4, 5, 7],
  7: [3, 5, 6],
};

// 입력
1 2

// 출력
6

 

 

미리 생각해 봐야할 것

• 너비우선 탐색을 이용
• 최장거리를 계산 프로그램 도식화 해보기(이런식의 거리계산으로 진행한다)

 

 

 

답

let graph = {
  1: [2, 3, 4],
  2: [1, 3, 4, 5, 6],
  3: [1, 2, 7],
  4: [1, 2, 5, 6],
  5: [2, 4, 6, 7],
  6: [2, 4, 5, 7],
  7: [3, 5, 6],
};

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

let queue = [start];
let visited = [];// 방문한 노드가 누적되게, 각각의 length를 구하면서 가장 큰값이 반환되도록함


function 최장거리(q, visited) {
  let node = q[q.length - 1];
  let length = 0;

  if (node == end) {
    return visited.length;
  }
  if (visited.includes(node)) {
    return visited.length;
  } else {
    visited.push(node);
  }
  let max = [];

  for (let i in graph[node]) {
    q.push(graph[node][i]);
    max.push(length, 최장거리(q, visited));

    length = Math.max.apply(null, max);

    queue.pop();
  }
  return length; //최댓값을 반환함
}

console.log(최장거리(queue, visited));