JS Coding Blog

음수 도로가 있어도 구하는 최소 배송 시간

자바스크립트 코딩테스트 문제로 bellman-ford 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

algorithm medium bellman-ford 함수명: shortestDeliveryTimes 제한 시간: 300ms

물류 거점 사이에 음수 시간이 있는 특수 도로가 있어도 시작 지점에서 각 거점까지의 최소 배송 시간을 구하는 그래프 문제입니다.

문제 설명

물류 거점은 1번부터 n번까지 번호가 붙어 있습니다.

roads[i] = [from, to, time]는 from 거점에서 to 거점으로 가는 단방향 도로가 있고, 그 도로를 지나는 데 time만큼 시간이 든다는 뜻입니다.

일부 특수 도로는 환승 보정 때문에 time이 음수일 수도 있습니다. 단, 시작 거점에서 도달 가능한 음수 사이클은 없다고 가정합니다.

시작 거점 start가 주어질 때, start에서 각 거점까지 가는 최소 시간을 순서대로 담은 배열을 반환하는 shortestDeliveryTimes 함수를 작성하세요.

  • 결과 배열은 start부터가 아니라 1번 거점부터 n번 거점까지 순서대로 담아야 합니다.
  • 도달할 수 없는 거점은 -1로 표시합니다.

제한사항

  • 2 <= n <= 200
  • 1 <= roads.length <= 5,000
  • 1 <= from, to <= n
  • from !== to
  • -10,000 <= time <= 10,000
  • 1 <= start <= n
  • 시작 거점에서 도달 가능한 음수 사이클은 없습니다.

예시

  • 입력: n = 5, roads = [[1,2,4],[1,3,5],[2,3,-2],[3,4,3],[2,5,6]], start = 1 → 출력: [0, 4, 2, 5, 10]
  • 입력: n = 4, roads = [[1,2,3],[2,3,-5],[3,4,2],[1,4,10]], start = 1 → 출력: [0, 3, -2, 0]
  • 입력: n = 4, roads = [[1,2,7]], start = 1 → 출력: [0, 7, -1, -1]
  • 입력: n = 3, roads = [[2,3,-4]], start = 2 → 출력: [-1, 0, -4]

힌트

  • 가중치가 모두 양수라면 다익스트라를 바로 떠올릴 수 있지만, 음수 간선이 섞이면 그 방식이 안전하지 않을 수 있습니다.
  • 어떤 도로를 이용해 더 짧아지는지를 여러 번 반복해서 갱신하는 방식이 필요합니다.
  • 최단 경로에서 한 정점을 중복 방문하지 않는 단순 경로는 최대 n - 1개의 간선만 사용합니다.

해설

이 문제의 핵심은 음수 가중치가 있어도 최단 경로를 구해야 한다는 점입니다.

이럴 때 대표적으로 쓰는 알고리즘이 Bellman-Ford입니다.

1. 기본 아이디어

  • dist[i]를 시작점에서 i번 거점까지 가는 현재까지 알려진 최소 시간이라고 둡니다.
  • 처음에는 start만 0, 나머지는 모두 Infinity로 시작합니다.
  • 그다음 모든 도로 [from, to, time]를 보면서:
    • dist[from] + time < dist[to]라면
    • dist[to]를 더 작은 값으로 갱신합니다.

이 과정을 모든 간선에 대해 최대 n - 1번 반복하면 최단 거리가 완성됩니다.

2. 왜 n - 1번이면 충분할까?

음수 사이클이 없으면 최단 경로는 같은 정점을 반복 방문하지 않는 단순 경로로 볼 수 있습니다. 정점이 n개라면 단순 경로에 들어갈 수 있는 간선 수는 최대 n - 1개입니다.

즉,

  • 1번째 반복이 끝나면 간선 1개로 갈 수 있는 최단 정보가 반영되고
  • 2번째 반복이 끝나면 간선 2개까지 쓰는 최단 정보가 반영되고
  • …
  • n - 1번째 반복이 끝나면 가능한 모든 최단 경로 길이가 반영됩니다.

3. 조기 종료

어떤 반복에서 단 한 번도 갱신이 일어나지 않았다면, 그 뒤 반복에서도 더 좋아질 값이 없습니다. 그래서 바로 멈추면 됩니다.

이 최적화를 넣으면 실제 실행 시간은 훨씬 줄어드는 경우가 많습니다.

4. 반환 형식 처리

문제는 1번부터 n번까지의 결과 배열을 요구합니다. 따라서 마지막에:

  • Infinity로 남아 있는 거점은 -1
  • 나머지는 실제 최소 시간

으로 바꿔서 반환하면 됩니다.

시간 복잡도는 O(n * roads.length)이고, 공간 복잡도는 O(n)입니다. 음수 간선이 있지만 음수 사이클은 없는 그래프에서 최단 경로를 구하는 대표 연습 문제입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.