๐Ÿง  codingtest/javascript 100์ œ

๋ฌธ์ œ 74. ์ตœ์žฅ ๊ฒฝ๋กœ ์ฐพ๊ธฐ

awesomeyelim 2022. 4. 13. 13:39
728x90

 

 

 

์ž…๋ ฅ๋ฐ›์€ ๋‘์ •์ ์ด ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์งˆ๋•Œ,

๋‘ ์ •์  ์‚ฌ์ด๋ฅผ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ์žฅ ๊ฑฐ๋ฆฌ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์—ฌ๋ผ.

  • ์ด๋•Œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ž€, ์ •์ ์˜ ์ค‘๋ณต์—†์ด ํ•œ ์ •์ ์—์„œ ๋‹ค๋ฅธ ์ •์ ๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ๋งŽ์€ ๊ฐ„์„ ์˜ ์ˆ˜๋ฅผ ์˜๋ฏธ

// ๋ฐ์ดํ„ฐ
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));