+1 2021 KAKAO BLIND RECRUITMENT 합승 택시 요금

문제 링크

import java.util.*;

class Edge implements Comparable<Edge>{
    int vtx;
    int cost;
    
    Edge(int v,int c){
        vtx = v;
        cost = c;
    }
    @Override
    public int compareTo(Edge e){
        return this.cost - e.cost;
    }
}

class Solution {
    static final int MAX = Integer.MAX_VALUE;
    static ArrayList<ArrayList<Edge>> graph;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = MAX;
        graph = new ArrayList<>();
        
        // graph 초기화
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<fares.length; i++){
            int v1 = fares[i][0], v2 = fares[i][1], cost = fares[i][2];
            graph.get(v1).add(new Edge(v2,cost));
            graph.get(v2).add(new Edge(v1,cost));
        }
        
        // 거리 배열 갱신 by dijkstra
        int[] distA = new int[n+1];
        int[] distB = new int[n+1];
        int[] distS = new int[n+1];
        
        Arrays.fill(distA,MAX);
        Arrays.fill(distB,MAX);
        Arrays.fill(distS,MAX);
        
        //Todo : refresh with dijkstra algorithms
        distA = dijkstra(a,distA);
        distB = dijkstra(b,distB);
        distS = dijkstra(s, distS);
        for(int i=1; i<=n; i++){
            answer = Math.min(answer, distS[i]+distA[i]+distB[i]);
        }
        return answer;
    }
    static int[] dijkstra(int start, int[] dist){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start,0)); // new 연산자로 새로 넣어줘야한다.
        dist[start] = 0;
        
        while(!pq.isEmpty()){
            Edge curNode = pq.poll();
            int curVtx = curNode.vtx;
            int curCost = curNode.cost;
            // 갱신 대상 아니면 패스
            if(curCost > dist[curVtx]) continue;
            
            // 갱신 대상인 경우 갱신
            ArrayList<Edge> edges = graph.get(curVtx);
            for(Edge edge :edges){
                int newCost = curCost + edge.cost; // edge.vtx로 가는 거리 계산
                if(newCost < dist[edge.vtx]){
                    dist[edge.vtx] = newCost;
                    pq.offer(new Edge(edge.vtx,newCost));
                }
            }
        }
        return dist;
    }
}

1. 객체 정렬 -> Comparable.compareTo Or comparator
2. PriorityQueue -> 기본적으로 최소 큐이다.
3. ArrayList로 정의된 객체에 접근할때 list[num]이 아닌 list.get(num)으로 접근한다.

import java.util.*;

class Edge implements Comparable<Edge> {
    public int vtx;
    public int cost;
    
    public Edge(int vtx, int cost){
        this.vtx = vtx;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Edge e){
        return this.cost - e.cost;
    }
}
class Solution {
    private ArrayList<ArrayList<Edge>> map = new ArrayList<>();
    // 이거 바꾸니까 되는거 보니까 답이 100001보다 큰 경우가있었떤 모양이다.
    int MAX_VALUE = Integer.MAX_VALUE; 
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        // 맵 초기화 및 값 할당
        for(int i=0; i<n+1; i++){
            map.add(new ArrayList<>());
        }
        for(int i=0; i<fares.length; i++){
            int[] cur = fares[i];
            map.get(cur[0]).add(new Edge(cur[1],cur[2]));
            map.get(cur[1]).add(new Edge(cur[0],cur[2]));
            
        }
        
        int[] distA = new int[n+1];
        int[] distB = new int[n+1];
        int[] distS = new int[n+1];
        
        Arrays.fill(distA,MAX_VALUE);
        Arrays.fill(distB,MAX_VALUE);
        Arrays.fill(distS,MAX_VALUE);
        
        // 다익스트라로 거리 배열 갱신
        distA=dijkstra(distA,a);
        distB=dijkstra(distB,b);
        distS=dijkstra(distS,s);
        
        //int ans = distA[s] + distB[s];
        int ans = MAX_VALUE;
        for(int i=1; i<n+1; i++){
            ans = Math.min(ans, distS[i]+distA[i]+distB[i]);
        }
        
        
        return ans;
    }
    public int[] dijkstra(int[] dist,int start){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start,0));
        dist[start] = 0;
        
        while(!pq.isEmpty()){
            Edge curE = pq.poll();
            int curCost = curE.cost;
            int curVtx = curE.vtx;
            
            if(dist[curVtx]<curCost) continue;
            
            for(Edge edge: map.get(curVtx)){
                int nextCost = curCost + edge.cost;
                int nextVtx = edge.vtx;
                
                if(nextCost< dist[nextVtx]){
                    pq.offer(new Edge(nextVtx, nextCost));
                    dist[nextVtx] = nextCost;
                }
            }
            
        }
        
        return dist;
    }
}

답이 최소이거나 최대 일때 초깃값 때문에 결정이 안될수도 있다.