최소비용 구하기

최소비용 구하기

문제 설명

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

예제 입력

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력

4

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 0;
  let N = Number(input[idx++]);
  let M = Number(input[idx++]);

  const graph = {};
  for (let i = 0; i <= N; i++) {
    graph[i] = [];
  }

  for (let i = 0; i < M; i++) {
    const [a, b, c] = input[idx++].split(" ").map(Number);
    graph[a].push({ to: b, cost: c });
  }

  const [start, end] = input[idx++].split(" ").map(Number);
  // 거리 정보를 담은 배열
  const dist = Array(N + 1).fill(Infinity);
  // 방문 체크용 배열
  const visited = Array(N + 1).fill(false);
  let answer = 0;
  // 시작 지점 초기화
  dist[start] = 0;

  const dijkstra = () => {
    // 결과 값
    let result = 0;
    for (let i = 0; i < N; i++) {
      // 현재값
      let now = -1;
      /**
       * 다익스트라 문제를 풀기위한 최소 값 설정
       * 그래프의 반복을 돌리면서 다음 좌표 값에 방문하지 않았고
       * 최소값 보다 다음 좌표의 거리가 작다면 갱신
       * */

      let min = Infinity;

      for (let j = 1; j <= N; j++) {
        if (!visited[j] && dist[j] < min) {
          min = dist[j];
          now = j;
        }
      }
      // 만약 현재 값이 변하지 않았다면(최소값을 찾지 못했다면) 종료
      if (now === -1) break;
      // 방문 체크
      visited[now] = true;
      // 다음 좌표 값 검사
      for (const next of graph[now]) {
        // 비용 계산 현재 좌표에서의 거리와 다음 좌표까지의 비용을 더해줌
        const newCost = dist[now] + next.cost;
        // 그 후 새로운 비용 값이 다음 좌표의 거리보다 작다면
        if (newCost < dist[next.to]) {
          // 갱신
          dist[next.to] = newCost;
        }
      }
    }
    // 마지막 좌표값 반환
    result = dist[end];
    return result;
  };
  answer = dijkstra();
  console.log(answer);
};
solution(input);

아이디어 / 접근법

1. 단방향 노드로 입력값 파싱하기
2. 시작 좌표 기준으로 다익스트라 수행
3. 다익스트라 함수를 통해 각 좌표에 해당하는 최소한의 거리를 dist 배열에 담기
4. 도착 지점의 거리 값 반환

후기

다익스트라 기본적인 문제였고, 시작 좌표 값과 끝 좌표 값이 주어지기 때문에 모든 좌표를 다 돌려볼 필요가 없었음 또, 일반 배열로 다익스트라를 돌려도 시간초과가 나지 않았는데, 입력값이 좀 더 커지거나 시간제한이 더 있다면 힙으로 구현하는 방안도 생각해봐야 할 것 같음 다익스트라 기본 문제였는데도 구글링을 좀 하면서 했음.