[javascript] 프로그래머스 level 3 - 합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

 

제한 사항

• 지점갯수 n은 3 이상 200 이하인 자연수입니다.
• 지점 s, a, b는 1 이상 n 이하인 자연수이며, 각기 서로 다른 값입니다.
• fares는 2차원 정수 배열입니다.
• fares 배열의 크기는 2 이상 n x (n-1) / 2 이하입니다.
• 출발지점 s에서 도착지점 a와 b로 가는 경로가 존재하는 경우만 입력으로 주어집니다.

---

문제 풀면서 어려웠던 점

• 방법이 생각 안남
• S -> A, S -> B 까지 각자 최적이랑 문제에서의 최적이랑 달라서 어떻게 해야할지 감이 안왔음

문제 풀이 방법

1. 먼저 거리담는 배열 arr생성 (모든 값 Infinity로 초기화)
2.  i -> i 는 0 으로 설정
3. arr에 fares 값들 반영
4. 플로이드 와셜(Floyd Warshall) 적용 (i가 중간지점, j가 시작지점, k가 끝지점)
5. min변수 Infinity로 초기화
6. 시작지점-중간지점 + 중간지점-A지점 + 중간지점-B지점이 최소인 값이 정답

---

코드

function solution(n, s, a, b, fares) {
    const arr = Array(n).fill(0).map(e=>[...new Array(n).fill(Infinity)])
    
    for(let i = 0; i < n; i++) {
        arr[i][i] = 0
    }
    
    fares.forEach(e=>{
        arr[e[1]-1][e[0]-1] = e[2]
        arr[e[0]-1][e[1]-1] = e[2]
    })
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n; j++) {
            for(let k = 0; k < n; k++) {
                if(arr[j][i] + arr[i][k] < arr[j][k]) {
                    arr[j][k] = arr[j][i] + arr[i][k]
                }
            }
        }
    }
    
    let min = Infinity
    
    for(let i = 0; i < n; i++) {
        const tmp = arr[s-1][i] + arr[i][a-1] + arr[i][b-1]
        if(min > tmp) min = tmp
    }
        
    return min;
}

---

배운 점

• 그래프 최단거리 -> 다익스트라.. 플로이드 .. 
• n이 200이면 플로이드 와셜 사용하면 됨