[백준1238_자바스크립트(javascript)] - 파티

🔴 문제

파티

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m, x], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const graph = Array.from({ length: n + 1 }, () => []);

for (const [s, e, c] of inputs) {
  graph[s].push([e, c]);
}

const getMinNode = (distances, visited) => {
  let minDistance = Infinity;
  let minNode = -1;

  for (let i = 1; i <= n; i++) {
    if (minDistance > distances[i] && !visited[i]) {
      minDistance = distances[i];
      minNode = i;
    }
  }

  return minNode;
};

const dijkstra = (start) => {
  const distances = Array(n + 1).fill(Infinity);
  const visited = Array(n + 1).fill(false);

  distances[start] = 0;

  while (true) {
    const currentNode = getMinNode(distances, visited);

    if (currentNode === -1) break;
    visited[currentNode] = true;

    for (const [node, cost] of graph[currentNode]) {
      if (distances[currentNode] + cost < distances[node]) {
        distances[node] = distances[currentNode] + cost;
      }
    }
  }

  return distances;
};

let ans = -1;
const backDijkstra = dijkstra(x);

for (let i = 1; i <= n; i++) {
  if (i === x) continue;

  const goDijkstra = dijkstra(i);

  const totalDistance = goDijkstra[x] + backDijkstra[i];
  if (totalDistance > ans) ans = totalDistance;
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

다익스트라 문제 유형!

X를 기준으로 다익스트라를 한번 수행하면 X번 마을에서 모든 마을까지 가는 최단거리를 찾을 수 있다.
그러면 1부터 N번까지의 마을을 모두 다익스트라를 수행해주면 각 마을부터 모든 마을 까지 가는 최단거리를 찾을 수 있다.
1부터 N까지 반복하면서 나온 결과에서 X번 마을의 최단거리 값과, X번 마을에서 해당 마을인i번째까지 가는 최단거리 값을 더하면 왕복 최단거리가 나오는데 이 값중 최대값을 출력해주면된다.
최단 거리를 구하는 방식은 일반적인 다익스트라 방식으로 관련 자세한 설명은 이곳에서 볼 수 있다.

🔵 Ref