Programmers Lv3, 합승 택시 요금[Java]

junto·2024년 7월 12일

Algorithms Graph programmers

programmers

목록 보기

48/66

문제

Programmers Lv3, 합승 택시 요금

핵심

정점은 최대 200개, 간선은 최대 100,000개가 존재한다.
무지와 어피치가 택시를 타고 각자 집에 귀가한다. 함께 탑승할 수 있을 때 최저 택시 요금을 구해야 한다. 택시 요금을 가중치로 보고, 최단 거리를 구하는 알고리즘을 적용할 수 있다.
가중치가 양수 일 때 적용할 수 있는 알고리즘은 다익스트라, 플루이드가 대표적이다.

1. 다익스트라

다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
해당 문제에 적용하면, 시작 지점(st)에서 함께 탑승하는 정점까지의 비용을 계산하고, 함께 탑승한 지점부터 각자의 집까지 비용을 계산한다.
함께 탑승하는 지점과 출발하는 지역이 같을 때 자연스럽게 탑승을 하지 않은 경우를 처리하게 된다.
음수 가중치가 존재한다면 벨만포드 알고리즘을 사용할 수 있다.

import java.util.*;

class Solution {

    List<int[]>[] adj = new ArrayList[204];

    public int solution(int n, int s, int a, int b, int[][] fares) {
        for (int i = 0; i <= n; ++i) adj[i] = new ArrayList<>();

        for (int i = 0; i < fares.length; ++i) {
            adj[fares[i][0]].add(new int[]{fares[i][2], fares[i][1]});
            adj[fares[i][1]].add(new int[]{fares[i][2], fares[i][0]});
        }

        int[] tgt = dijkstra(s, n);
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; ++i) {
            int[] aln = dijkstra(i, n);
            int cost = tgt[i] + aln[a] + aln[b];
            ans = Math.min(ans, cost);
        }
        return ans;
    }

    int[] dijkstra(int st, int n) {
        int[] d = new int[n + 1];
        Arrays.fill(d, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        d[st] = 0;
        pq.add(new int[]{d[st], st});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int curWeight = cur[0];
            int curNode = cur[1];

            if (d[curNode] != curWeight) continue;

            for (var nxt : adj[curNode]) {
                int nxtWeight = nxt[0];
                int nxtNode = nxt[1];

                if (d[nxtNode] <= d[curNode] + nxtWeight) continue;
                d[nxtNode] = d[curNode] + nxtWeight;
                pq.add(new int[]{d[nxtNode], nxtNode});
            }
        }
        return d;
    }
}

시간복잡도

$O(N * (N+E)logN)$

2. 플로이드

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다.
마찬가지로 함께 가는 경로, 함께 간 경로에서부터 각자 집까지의 경로 비용을 더하면 된다.
음수인 가중치가 있어도 사용할 수 있지만, 음수인 사이클이 존재할 때는 사용할 수 없다는 것을 명심하자.

import java.util.*;

class Solution {
    
    int INF = 0x1fffffff;
    int dist[][] = new int[204][204];

    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        for (int i = 1; i <= n; ++i) { 
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
        
        for (int i = 0; i < fares.length; ++i) {
            dist[fares[i][0]][fares[i][1]] = fares[i][2];
            dist[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (i == j) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        int ans = Integer.MAX_VALUE;
        for (int tot = 1; tot <= n; ++tot) {    
            ans = Math.min(ans, dist[s][tot] + dist[tot][a] + dist[tot][b]);
        }
        return ans;
    }
}