합승 택시 요금 - JAVA, 다익스트라 알고리즘(Dijkstra Algorithm)

 

 

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

프로그래머스

 

 

 

풀이 - 나의 생각

전형적인 다익스트라 알고리즘에다가

 

비교연산 한 번이 추가 된 문제입니다.

 

무지와 어파치가 각자의 목적지 'A' 와 'B'에

 

최소한의 비용으로 가는 방법을 알기 위해서는

 

결국에 모든 목적지에 최소한의 비용으로 가는 방법을 알아야합니다.

 

그렇기에

 

int[] distFromStart = dijkstra(graph, n, s);
int[] distFromA = dijkstra(graph, n, a);
int[] distFromB = dijkstra(graph, n, b);

 

우선 출발지에서 모든 지점으로의 최소 비용을 구합니다.

A와 B에서 모든 지점의 최소 비용을 구합니다.

 

그 후 세가지 경우의 합을 비교합니다.

 

그 이유는

 

우리가 고려해야하는 경우는

 

1. 일정 지점까지 동행 후, 그 지점부터 각자의 목적지를 가는 경우

 

2. 처음부터 각자 가는 경우

 

두가지 입니다.

 

출발지에서 시작하는 다익스트라는 일정 지점까지 동행하는 경우를,

 

A, B에서 출발하는 다익스타는 일정 지점에서부터 각자가 간 경우를 알 수 있게 합니다.

 

그렇기에 세개의 배열의 합은

 

목적지까지의 비용을 나타내게 되는겁니다.

 

 

코드

 

import java.util.*;

class Node implements Comparable<Node>{
    int index;
    int cost;
    
    public Node(int index, int cost){
        this.index = index;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node other){
        return Integer.compare(this.cost, other.cost);
    }
}

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] graph = new int[n+1][n+1];
        //그래프 초기화 및 값 입력
        for(int i = 1; i <= n; i++){
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }
        for(int[] fare : fares){
            graph[fare[0]][fare[1]] = fare[2];
            graph[fare[1]][fare[0]] = fare[2];
        }
        
        int[] distFromStart = dijkstra(graph, n, s);
        int[] distFromA = dijkstra(graph, n, a);
        int[] distFromB = dijkstra(graph, n, b);
        
        int minCost = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            if(distFromStart[i] != Integer.MAX_VALUE && distFromA[i] != Integer.MAX_VALUE && distFromB[i] != Integer.MAX_VALUE){
                minCost = Math.min(minCost, distFromStart[i] + distFromA[i] + distFromB[i]);
            }
        }
        
        return minCost;
    }
    
    private int[] dijkstra(int[][] graph, int n, int start){
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int current = node.index;
            int cost = node.cost;
            
            //가야할 곳의 비용이 기존의 비용보다 비싸면 pass
            if(cost > dist[current]) continue;
            
            for(int i = 1; i <= n; i++){
            	//자기 자신의 위치, 연결이 안된 곳은 pass
                if(graph[current][i] == Integer.MAX_VALUE) continue;
                
                int newDist = cost + graph[current][i];
                //새로운 최소 비용일 시 갱신
                if(newDist < dist[i]){
                    dist[i] = newDist;
                    pq.add(new Node(i, newDist));
                }
            }
        }
        
        return dist;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요