9. 최단 경로

🥝 미래 도시

입력

5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

4 2
1 3
2 4
3 4

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

// Run by Node.js
const { count } = require("console");
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let inputArr = [];
rl.on("line", function (line) {
  inputArr.push(line);
}).on("close", function () {
  solution();
  process.exit();
});

const solution = () => {
  for (let i = 0; i < inputArr.length; i++) {
    inputArr[i] = inputArr[i].split(" ");
    for (let j = 0; j < 2; j++) {
      inputArr[i][j] = parseInt(inputArr[i][j]);
    }
  }
  const firstLine = inputArr.shift();
  const lastLine = inputArr.pop();
  let [n, m] = [firstLine[0], firstLine[1]];
  let [x, k] = [lastLine[0], lastLine[1]];
  let graph = Array.from(Array(n + 1), () =>
    Array(n + 1).fill(Number.MAX_SAFE_INTEGER)
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      if (i === j) graph[i][j] = 0;
    }
  }
  for (let [a, b] of inputArr) {
    graph[a][b] = 1;
    graph[b][a] = 1;
  }
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      for (let s = 1; s <= n; s++) {
        graph[j][s] = Math.min(graph[j][s], graph[j][i] + graph[s][i]);
      }
    }
  }
  let distance = graph[1][k] + graph[k][x];
  if (distance >= Number.MAX_SAFE_INTEGER) console.log(-1);
  else console.log(distance);
};

구현할 때 개선점

• 한 줄 평
  More Info: 벨로그 링크

🥝

입력