무료 패스 한 번으로 가는 최소 비용 경로
자바스크립트 코딩테스트 문제로 layered-graph 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
도시를 이동하는 동안 도로 하나에만 무료 패스를 사용할 수 있을 때, 출발점에서 도착점까지의 최소 비용을 구하는 solution 함수를 작성하세요.
무료 패스는 최대 한 번 사용할 수 있으며, 어떤 도로 하나를 선택해 그 도로의 비용을 0으로 만들 수 있습니다.
패스를 꼭 써야 하는 것은 아닙니다.
제한사항
n은 도시의 개수이며 도시는1번부터n번까지 번호가 붙어 있습니다.1 <= n <= 1000000 <= edges.length <= 200000edges[i] = [from, to, cost]- 각 도로는 단방향입니다.
1 <= from, to <= nfrom !== to1 <= cost <= 1000000000start,end는1이상n이하의 정수입니다.- 출발 도시에서 도착 도시로 갈 수 없으면
-1을 반환합니다. start === end라면 이동하지 않아도 되므로0을 반환합니다.
예시
- 입력:
n = 5,edges = [[1, 2, 4], [2, 3, 7], [1, 3, 15], [3, 4, 3], [4, 5, 2], [2, 5, 20]],start = 1,end = 5→ 출력:5 - 입력:
n = 4,edges = [[1, 2, 5], [2, 4, 5], [1, 3, 100], [3, 4, 1]],start = 1,end = 4→ 출력:1 - 입력:
n = 4,edges = [[1, 2, 3], [3, 4, 4]],start = 1,end = 4→ 출력:-1
힌트
- 어떤 도시에 도착했는지만으로는 상태가 충분하지 않습니다.
- 같은 도시라도 무료 패스를 이미 쓴 상태와 아직 안 쓴 상태는 이후 선택지가 다릅니다.
- 최단 경로 알고리즘을 쓸 때 상태를 하나 더 늘려 보세요.
해설
이 문제의 핵심은 정점 번호만으로는 최단 거리 상태를 구분할 수 없다는 점입니다.
예를 들어 같은 3번 도시에 도착했더라도,
- 아직 무료 패스를 안 쓴 상태
- 이미 어떤 도로에서 무료 패스를 쓴 상태
이 둘은 이후 이동 비용이 달라질 수 있으므로 서로 다른 상태로 다뤄야 합니다.
가장 자연스러운 방법은 상태를 2배로 확장한 다익스트라입니다.
dist[city][0]: 아직 무료 패스를 쓰지 않고city에 도착하는 최소 비용dist[city][1]: 이미 무료 패스를 한 번 쓰고city에 도착하는 최소 비용
현재 상태가 (city, used)일 때 도로 [city, next, cost]를 따라 이동하는 방법은 두 가지입니다.
- 패스를 쓰지 않고 이동
- 다음 상태는
(next, used) - 비용은
+ cost
- 다음 상태는
- 아직 패스를 안 썼다면 지금 이 도로에서 사용
- 현재
used === 0일 때만 가능 - 다음 상태는
(next, 1) - 비용은
+ 0
- 현재
이렇게 하면 원래 그래프를 “패스 사용 전 레이어”와 “패스 사용 후 레이어” 두 장으로 나눈 것과 같습니다. 각 상태를 우선순위 큐에 넣고 가장 작은 비용부터 꺼내면 됩니다.
최종 정답은 dist[end][0]과 dist[end][1] 중 더 작은 값입니다.
둘 다 무한대라면 도달할 수 없으므로 -1입니다.
이 방식은 간선마다 최대 두 번의 완화(relax)를 시도하므로,
우선순위 큐를 사용하면 전체적으로 O((n + m) log n) 수준에서 해결할 수 있습니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.