프로그래머스: 합승 택시 요금 - javascript(플로이드 와샬 알고리즘)

문제 출처 

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

프로그래머스

 

문제 풀이 힌트 

 

플로이드 와샬 알고리즘을 사용하면 참 간단한 문제다 ! 

 

코드는 간단한데, 주석을 작성하느라 좀 길어졌다. 

 

정답 풀이 코드 

function solution(n, s, a, b, fares) {

 //해당 node => node 로 향하는 최소 비용을 갱신할 2차원 배열 생성
   const board = Array.from({length: n}).map(() => new Array(n).fill(Infinity)); //Infinity로 채우는 이유: 아래에서 설명 
  
  //자기 자신에게 향하는 곳은 비용이 0이다. (2번 node => 2번 node는 거리가 0)
    for(let i=0; i<n; i++){
        board[i][i] = 0; 
    }
  //주어진 fares로 board 초기 set해준다.   
    fares.forEach((pos) => {
        const [x,y, weight] = pos; 
        board[x-1][y-1] = weight; //node가 1부터 있지만 board는 0부터 시작이니 각각 1씩 빼줘야 한다. 
        board[y-1][x-1] = weight; 
    })
  
  //Infinity로 값 채운 이유 
  //그럼 node 1=> node2 로 가는 간선이 없는건? Infinity로 채운다. 아래 반복문에서 비용이 적은걸로 계속 갱신을 해줄건데, 간선이 없는 곳은 무한으로 설정함으로써 계산에서 제외되게끔 한다. 
  
  //k는 거쳐가는 정점, i는 시작 정점, j는 도착 정점 
    for(let k=0; k<n; k++){ 
        for(let i=0; i<n; i++){
            for(let j=0; j<n; j++){
                if(board[i][k] + board[k][j] < board[i][j]){ //만약 i => j로 가는 것보다,  i => k => j로 가는 것이 더 싸다면?
                    board[i][j] = board[i][k] + board[k][j]; //i => k => j 비용으로 갱신해준다.  
                }
            }
        }
    }
    //아예 각각 혼자 갈 때의 값을 answer로 미리 채운다. (s => a의 최솟값) + (s=> b의 최솟값)
    let answer = board[s-1][a-1] + board[s-1][b-1]; 
    
    //해당 정점(i)까지 같이 가고, 나머지는 각자 갈 때의 합을 계산한다. 
    //계속 최솟값으로 갱신 
    for(let i=0; i<n; i++){ //어디 i까지 함께갈까? 
       let shortest = board[s-1][i] + board[i][a-1] + board[i][b-1]; //board[s-1][i]: i까지 같이 갈 때 비용 , board[i][a-1]: i부터 a까지 비용, board[i][b-1] : i부터 b까지 비용 
       answer = Math.min(answer, shortest) //더 싼 가격을 answer에 계속 갱신 
    }
    return answer 
}

 

ONly 정답 코드 

function solution(n, s, a, b, fares) {
   const board = Array.from({length: n}).map(() => new Array(n).fill(Infinity)); 
  
    for(let i=0; i<n; i++){
        board[i][i] = 0; 
    }
    
    fares.forEach((pos) => {
        const [x,y, weight] = pos; 
        board[x-1][y-1] = weight; 
        board[y-1][x-1] = weight; 
    })
    
    for(let k=0; k<n; k++){
        for(let i=0; i<n; i++){
            for(let j=0; j<n; j++){
                if(board[i][k] + board[k][j] < board[i][j]){
                    board[i][j] = board[i][k] + board[k][j]; 
                }
            }
        }
    }
    let answer = board[s-1][a-1] + board[s-1][b-1]; 
    for(let i=0; i<n; i++){
       let shortest = board[s-1][i] + board[i][a-1] + board[i][b-1]; 
       answer = Math.min(answer, shortest)
    }
    return answer 
}

 

알고가는 ppoint