[JAVA] 합승 택시 요금

문제

코딩테스트 연습 - 합승 택시 요금

 

해결 방법

요즘 코딩 테스트를 볼 때 프로그래머스를 많이 이용하기에, 적응을 위해 프로그래머스 문제를 조금 풀어보고 있다.

집까지 가는 최소 비용의 길을 찾는 문제인데, 도착 지점이 두 곳이다.

문제에서 보면 시작점에서 일정 지점까지는 같이 택시를 타고 이동하고, 그 지점부터 각자 택시를 타고 집에 간다고 하며, 시작점에서 함께 이동하지않고 각자 택시를 가고 집에 가는 비용이 더 저렴하다면 그렇게 해도 상관없다고 한다.

 

처음에 문제를 봤을 때 다익스트라를 활용하면 되겠다고 생각이 들었다.

근데 다익스트라는 구현할 때 시작점이 필요한데, S, A, B의 각각의 최소 비용의 길이 어디인지 모두 필요하기 때문에 각각 다익스트라를 활용하여 최소 비용을 배열에 넣어주기로 했다.

 

그 뒤에 정점의 갯수인 n을 사용해서 1부터 n까지 반복문을 돌려 어느 정점을 들려서 가는 것이 가장 비용에 적게 드는지 찾은 뒤 답을 return하여 주었다.

이 반복문을 통하면 처음부터 각자 택시를 타고 가는 경우도 체크를 하게 되는데 그 까닭은 체크하는 정점 중에 출발점에 해당하는 정점이 있을 것이고, S에서 시작한 최소 비용 배열은 S가 도착점일 때는 0이기 때문에 출발점에서 A와 B로 향하는 비용만 계산이 되기 때문이다.

 

즉, 코드에서 보면 출발점의 최소 비용 배열은 dpS, A지점은 dpA, B지점은 dpB일 때 출발지가 s라고 한다.

그럼 dpS[s] = 0이고, dpA[s]와 dpB[s]는 s지점에서 A, B지점까지의 최소 비용이 저장되어있어 각자 출발지에서 따로 택시를 타고 이동한 값이 나오게 된다.

 

 

코드

import java.util.*;

class Solution {
    static ArrayList<Node> list[];
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < fares.length; i++) {
            int start = fares[i][0];
            int end = fares[i][1];
            int cost = fares[i][2];
            
            // 양방향 통행이 가능함
            list[start].add(new Node(end, cost));
            list[end].add(new Node(start, cost));
        }
        
        int[] dpS = new int[n + 1];
        int[] dpA = new int[n + 1];
        int[] dpB = new int[n + 1];
        Arrays.fill(dpS, Integer.MAX_VALUE);
        Arrays.fill(dpA, Integer.MAX_VALUE);
        Arrays.fill(dpB, Integer.MAX_VALUE);
        
        dpS = findRoute(s, dpS);
        dpA = findRoute(a, dpA);
        dpB = findRoute(b, dpB);
        
        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
        // 각 정점을 들려 각자의 지점까지 가는 비용 중 최소인 값 찾기
            answer = Math.min(answer, dpS[i] + dpA[i] + dpB[i]);
        }
        
        return answer;
    }
    static int[] findRoute(int start, int[] dp) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start, 0));
        dp[start] = 0;
        
        while (!q.isEmpty()) {
            Node node = q.poll();
            for (int i = 0; i < list[node.next].size(); i++) {
                int next = list[node.next].get(i).next;
                int cost = list[node.next].get(i).cost;
                
                if (dp[next] > node.cost + cost) {
                    dp[next] = node.cost + cost;
                    q.offer(new Node(next, dp[next]));
                }
            }
        }       
        return dp;
    }
}

class Node implements Comparable<Node> {
    int next;
    int cost;
    
    Node (int next, int cost) {
        this.next = next;
        this.cost = cost;
    }
    
    @Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return cost - o.cost;
	}
}