합승택시요금.md

🚕 합승 택시 요금

난이도: Lv.3
소요 시간: 31분
메모리: --KB
시간: --ms

리뷰

• 다익스트라로 문제를 풀었다
• s, a, b를 시작노드로 해서 다익스트라로 최단경로를 구함
• 합승하지 않는 경우(s->a, s->b 경로값 더함)를 기본으로 생각
• 합승한 경우(s->t, t->a, t->b 경로값 더함)를 비교하면서 최소비용을 구함
• t->a의 경우, 그래프 방향이 없으니까 a->t로 비용을 구함

전체 코드

class Solution_72413_합승택시요금 {
    int[][] d;

    public int solution(int n, int s, int a, int b, int[][] fares) {
       d = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i!=j) d[i][j] = 987654321;
            }
        }
        for(int[] fare : fares){
            d[fare[0]][fare[1]] = d[fare[1]][fare[0]] = fare[2];
        }

        dijkstra(s,n);
        dijkstra(a,n);
        dijkstra(b,n);


        int answer = d[s][a] + d[s][b];

        for (int i = 1; i <= n; i++) {
            if(d[s][i]!=987654321 && d[a][i] !=987654321 && d[b][i] !=987654321){
                int tmp = d[s][i] + d[a][i] + d[b][i];
                if (tmp < answer) answer = tmp;
            }
        }
        return answer;
    }

    void dijkstra (int target, int n){
        boolean[] v = new boolean[n+1];
        v[target] = true;
        int cnt = 1;

        while(cnt++ < n){
            int min = 987654321;
            int idx = 0;
            for(int j=1; j<=n ; j++){
                if(!v[j] && d[target][j] < min){
                    min = d[target][j];
                    idx = j;
                }
            }
            if(min==987654321) return;
            v[idx] = true;
            for(int j=1; j<=n; j++){
                if(!v[j] && d[target][idx] + d[idx][j] < d[target][j]){
                    d[target][j] = d[target][idx] + d[idx][j];
                }
            }
        }
    }
}