programmers_KAKAO2021Blind 합승 택시 요금 javascript

=> 2주 후 필히 다시 풀기!!!

감이 오지 않아, 다른 사람의 풀이를 먼저 보았다..

다익스트라or플루이드 와샬로 풀리는 문제라고 한다.

슬슬 고급 알고리즘 문제를 풀어봐야 할듯하다.

문제 풀이는 그래프 알고리즘을 적용하면 아주 쉬워 진다.

<플루이드 와샬 풀이>

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

    const board=[...Array(n+1)].map(()=>[...Array(n+1)].map(()=>Infinity));

    
    fares.forEach(fare=>{
        board[fare[0]][fare[1]]=fare[2];
        board[fare[1]][fare[0]]=fare[2];
    })
    
    for(var i=1;i<=n;i++){
        board[i][i]=0;
    }

    for(var k=1;k<=n;k++){
        for(var i=1;i<=n;i++){
            for(var j=1;j<=n;j++){
                if(board[i][j]>board[i][k]+board[k][j]){
                    board[i][j]=board[i][k]+board[k][j];
                }
                
            }
        }
    }
    
    
    var shortest=board[s][a]+board[s][b];
    
    for(var i=1;i<=n;i++){
        shortest=Math.min(shortest,board[s][i]+board[i][a]+board[i][b]);
    }
    

    return shortest;
}

<다익스트라 풀이>

function solution(n, s, a, b, fares) {
    var answer = Infinity;

    const map = [...Array(n+1)].map(()=>[...Array(n+1)].map(()=>Infinity));

    fares.forEach(([start, end, dist]) => {
        map[start][end] = map[end][start] = dist;
    });
    
    for(var i=1;i<=n;i++){
        map[i][i]=0;
    }

    /*n: 지점의 갯수, s: 출발지점 나타냄, a: A의 도착지점 ,b: B의.. , 도착지점을 출발지점으로 사용**/
    const distFromA = findDistToAllNodes(n, map, a);
    
    const distFromB = findDistToAllNodes(n, map, b);
    const distFromS = findDistToAllNodes(n, map, s);
    
    for(var i=1;i<=n;i++){
        answer=Math.min(answer,distFromS[i]+distFromA[i]+distFromB[i]);
    }

    return answer;

}

function findDistToAllNodes(n, map, node) {//지점의 개수, map, 출발지점

    const visit = [...Array(n+1)].map(()=>false);
    
    let lastVisit = node;//출발지점.
    
    let dist=[...map[node]];//출발지점에서 인접 노드까지 거리
    
    visit[node]=true;//출발 노드 방문 처리.

    
    for(var k=1;k<=n-2;k++){
        
        let min=Infinity;//선택하지 않은 노드 중 가장 가까운 인접 노드 찾기.
        let index=0;
        for(var i=1;i<=n;i++){
            if(min>dist[i]&&!visit[i]){
                min=dist[i];
                index=i;
            }
        }
        visit[index]=true;
        
        for(var i=1;i<=n;i++){
            if(!visit[i]){
               if(dist[i]>dist[index]+map[index][i]){
                    dist[i]=dist[index]+map[index][i];   
                }            
            }
        }
        
    }

    return dist;
}