모든 정류장 쌍의 최소 이동 요금

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

algorithm medium floyd-warshall 함수명: solution 제한 시간: 400ms

정류장 개수 n과 단방향 이동 요금 정보 fares가 주어질 때, 모든 출발 정류장에서 모든 도착 정류장까지 가는 최소 요금을 2차원 배열로 반환하는 solution 함수를 작성하세요.

도달할 수 없는 경우는 -1로 표시합니다.

제한사항

1 <= n <= 100
0 <= fares.length <= 5000
fares[i] = [from, to, cost]
0 <= from, to < n
from !== to
1 <= cost <= 10000
같은 방향의 요금 정보가 여러 번 주어질 수 있습니다.
반환값은 n x n 크기의 2차원 배열입니다.
자기 자신으로 가는 최소 요금은 항상 0입니다.

예시

입력:

4,
[
  [0, 1, 4],
  [0, 2, 10],
  [1, 2, 3],
  [2, 3, 2],
  [1, 3, 9]
]

출력:

[
  [0, 4, 7, 9],
  [-1, 0, 3, 5],
  [-1, -1, 0, 2],
  [-1, -1, -1, 0]
]

0 -> 2는 직접 가면 10이지만 0 -> 1 -> 2로 가면 7입니다.
1 -> 3은 직접 가면 9이지만 1 -> 2 -> 3으로 가면 5입니다.

입력: 3, [] 출력:

[
  [0, -1, -1],
  [-1, 0, -1],
  [-1, -1, 0]
]

힌트

모든 정점 쌍 사이 최단 거리를 한 번에 구하는 대표 알고리즘이 있습니다.
먼저 dist[i][j]를 직접 가는 비용으로 채우고, 없으면 아주 큰 값으로 두세요.
어떤 정류장 k를 중간 경유지로 허용했을 때 i -> k -> j가 더 싼지 비교해 갱신해 보세요.

해설

이 문제는 Floyd-Warshall 알고리즘의 전형적인 연습 문제입니다.

핵심은 dist[i][j]를 “현재까지 알고 있는 i에서 j까지의 최소 요금”으로 두고, 중간에 들를 수 있는 정류장을 하나씩 늘려 가며 답을 갱신하는 것입니다.

n x n 거리 배열을 만듭니다.
- dist[i][i] = 0
- 직접 가는 간선이 있으면 그 비용
- 없으면 충분히 큰 값(Infinity 같은 값)
같은 방향 간선이 여러 번 들어올 수 있으므로, 처음 채울 때는 더 작은 비용만 남겨야 합니다.
이제 중간 정류장 k를 0부터 n - 1까지 하나씩 허용합니다.
- 모든 (i, j)에 대해 dist[i][j] > dist[i][k] + dist[k][j] 이면 갱신합니다.
이 과정을 마치면 모든 정류장 쌍의 최소 요금이 채워집니다.
- 끝까지 큰 값으로 남아 있던 칸은 도달 불가능이므로 -1로 바꿉니다.

왜 이 방식이 맞을까요?

어떤 최단 경로도 “중간에 사용할 수 있는 정류장 집합”을 기준으로 생각할 수 있습니다.
k번째 단계에서는 0..k번 정류장만 경유지로 쓰는 최단 경로가 모두 반영됩니다.
그래서 마지막 단계가 끝나면 모든 정류장을 경유지로 허용한 전체 최단 경로가 완성됩니다.

시간 복잡도는 O(n^3)이고, n <= 100 범위에서는 충분히 사용할 수 있습니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

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

댓글

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