[백준1719_자바스크립트(javascript)] - 택배

🔴 문제

택배

🟡 Sol

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

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

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

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

  for (let i = 1; i <= n; i++) {
    if (!visited[i] && minDistance > distances[i]) {
      minNode = i;
      minDistance = distances[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 node = getMinNode(visited, distances);

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

    for (const [next, cost] of graph[node]) {
      if (distances[next] > distances[node] + cost) {
        distances[next] = distances[node] + cost;
        map[start][next] = map[start][node] !== '-' ? map[start][node] : next;
      }
    }
  }
};

for (let i = 1; i <= n; i++) {
  dijkstra(i);
}

for (let i = 1; i <= n; i++) {
  let ans = '';

  for (let j = 1; j <= n; j++) {
    ans += map[i][j] + ' ';
  }
  console.log(ans.trim());
}

🟢 풀이

⏰ 소요한 시간 : -

그래프의 연결 정보가 주어지고, 최단거리로 갈 때 가장 첫번째로 마주치는 노드를 구하는 문제다.
노드마다 가중치가 다르기 때문에 최단거리를 구하기 위해서 다익스트라를 사용했다.
정답을 저장할 배열과, 그래프의 연결 정보를 저장할 배열을 초기화한다.
그래프의 연결 정보를 저장하는데 양방향 그래프이므로 다음과 같이 graph를 초기화 했다.

graph[s].push([e, c]);
graph[e].push([s, c]);

1번노드부터 n번노드까지 다익스트라를 수행해 최단거리를 구해준다.

다익스트라 함수는 start 노드를 매개변수로 받아 start 노드로부터 각 정점으로 가는 최단거리를 구해준다.

거리 정보를 저장할 distances 배열, 방문정보를 저장할 visited 배열을 각각 초기화 해준뒤, 시작노드 start를 0으로 초기화한다.

getMinNode 함수는 distances 배열과 visites 배열을 전달받아 거리가 가장 작고, 방문하지 않은 노드를 리턴한다. 이 함수로부터 다음에 방문할 노드를 정해 다익스트라 로직을 수행해준다.

for (const [next, cost] of graph[node]) {
      if (distances[next] > distances[node] + cost) {
        distances[next] = distances[node] + cost;
        map[start][next] = map[start][node] !== '-' ? map[start][node] : next;
      }
}

이 부분에서는 정답을 저장할 배열도 같이 채워준다.
map[start][next]는 start → next로 가는 경로에서 가장 처음 거쳐야 하는 노드를 의미한다.

만약 map[start][node]가 -라면 start → node까지 직행이므로, 다음 노드인 next를 직접 연결된 경로로 본다.
반면 map[start][node]가 이미 존재한다면, start → node까지의 첫 경유지가 정해져 있으므로, 캐싱된 경로 값을 사용한다.

마지막으로 출력 형태에 맞게 정답을 출력하면 끝

🔵 Ref