프로그래머스 - [Level 3] 합승 택시 요금(JAVA)

프로그래머스 합승 택시 요금[2021 카카오 블라인드]

카테고리 : 다익스트라/플로이드 와샬

다익스트라, 플로이드와샬 알고리즘을 적용해 풀이할 수 있다.

1) 정점 s, a, b를 출발점으로 잡고, 최소 이동경로를 costs 배열에 저장한다.

이때, 출발점을 1<= 출발점 <=n(모든 노드)
로 잡았을 때 '시간초과'가 발생했다.

s, a, b 를 출발점으로 잡고 최소 이동경로를 구하기만해도 
모든 정점에서 s, a, b로 이동하는 비용을 기억할 수 있다.
(문제에서 요구하는 모든 경우의 수를 체크할 수 있다.)

2) 합승을 하지 않고 이동하는 경우와 합승을 하고 이동하는 경우의 최소 비용을 return 한다.

'costs[시작점][경유지점]+costs[경유지점][A도착지]+costs[경유지점][B도착지]'

이때, 시작점 => 경유지점은 합승을 하는 구간이고
경유지점 => 도착점 A , 경유지점 => 도착점 B 는 따로 이동하는 구간이다.

따라서, 경유할 수 있는 모든 지점을 돌면서
최소비용을 갱신하면 답을 도출할 수 있다.

소스 코드

import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    
    static int[][] board;
    static int[][] costs;
    static ArrayList<ArrayList<Integer>> list=new ArrayList<>();
    
    static class Node{
        int loc,cost;
        
        Node(int loc,int cost){
            this.loc=loc;
            this.cost=cost;
        }
    }
    
    static void init(int start,int n,int[][] fares){
        board=new int[n+1][n+1];
        costs=new int[n+1][n+1];
        
        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
            Arrays.fill(costs[i],987654321);
            costs[i][i]=0;
        }
        
        for(int i=0;i<fares.length;i++){
            int s=fares[i][0],e=fares[i][1];
            list.get(s).add(e);
            list.get(e).add(s);
            board[s][e]=fares[i][2];
            board[e][s]=fares[i][2];
        }
        return;
    }
    
    
    static void calcMinCost(int start){
        
        Queue<Node> queue=new LinkedList<>();
        queue.add(new Node(start,0));
        
        while(!queue.isEmpty()){
            Node node=queue.poll();
            int now_loc=node.loc,cost=node.cost;
            
            for(int i=0;i<list.get(now_loc).size();i++){
                int next_loc=list.get(now_loc).get(i);
                int next_cost=board[now_loc][next_loc]+cost;
                
                if(costs[start][next_loc]>next_cost){
                    costs[start][next_loc]=next_cost;
                    costs[next_loc][start]=next_cost;
                
                    queue.add(new Node(next_loc,next_cost));
                }
            }
        }
    }
   
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        init(s,n,fares);
        
        calcMinCost(s);
        calcMinCost(a);
        calcMinCost(b);
        
        answer=costs[s][a]+costs[s][b];
        
        for(int mid=1;mid<=n;mid++){
            if(costs[s][mid]==987654321 || costs[mid][a]==987654321 || costs[mid][b]==987654321) continue;
            
            answer=Math.min(answer,costs[s][mid]+costs[mid][a]+costs[mid][b]);   
        }
        return answer;
    }
}