EunSung.log

[프로그래머스] 합승 택시 요금

4 min read

Notice

문제 정보

풀이

거의 전형적인 최단 경로 알고리즘 문제로, dijkstra나 Floyd-Warshall 알고리즘을 사용하면 된다.

정확성 뿐만 아니라 효율성 테스트도 있는 문제지만, n이 최대 200이기 때문에 Floyd-Warshall로도 풀 수 있다.

코딩 문제를 풀 때 초당 연산 횟수는 1000만에서 3000만 정도로 고려해서 시간 복잡도를 생각하면 된다는데1, Floyd-Warshall 알고리즘의 시간 복잡도는 으로 연산을 최대 800만번 수행하기 때문이다.

그렇기에 실제 코딩 테스트 환경이었다면 dijkstra가 더 효율적일지언정 구현이 간단한 Floyd-Warshall 알고리즘이 좋을 것 같다.

코드

Floyd-Warshall 알고리즘

import java.util.*;
 
class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        final int MAX_COST = 200 * 100000 + 1;
        int[][] cost = new int[n+1][n+1];
   
        for (int i = 1; i <= n; i++) {
            Arrays.fill(cost[i], MAX_COST);
            cost[i][i] = 0;
        }
        
        for (int i = 0; i < fares.length; i++) {
            int start = fares[i][0];
            int end = fares[i][1];
            int fare = fares[i][2];
            
            cost[start][end] = fare;
            cost[end][start] = fare;
        }
        
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) 
                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
        
        int answer = cost[s][a] + cost[s][b];
        
        for (int i = 1; i <= n; i++)
            answer = Math.min(answer, cost[s][i] + cost[i][a] + cost[i][b]);
        
        return answer;
    }
}

dijkstra 알고리즘

import java.util.*;
 
class Solution {
    static final int MAX_COST = 200 * 100000 + 1;
    
    class Node implements Comparable<Node> {
        int vertex;
        int cost;
        
        Node(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    public int solution(int n, int s, int a, int b, int[][] fares) {
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());
        
        for(int[] fare: fares) {
            int start = fare[0];
            int end = fare[1];
            int cost = fare[2];
            
            graph.get(start).add(new Node(end, cost));
            graph.get(end).add(new Node(start, cost));
        }
        
        int[] startA = dijkstra(n, a, graph);
        int[] startB = dijkstra(n, b, graph);
        int[] start = dijkstra(n, s, graph);
        
        int answer = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++)
            answer = Math.min(answer, startA[i] + startB[i] + start[i]);
        
        return answer;
    }
    
    private int[] dijkstra(int n, int start, List<List<Node>> graph) {
        int[] cost = new int[n + 1];
        Arrays.fill(cost, MAX_COST);
        cost[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int curVertex = current.vertex;
            int curCost = current.cost;
            
            if (curCost > cost[curVertex]) continue;
            
            for (Node next : graph.get(curVertex)) {
                int nextVertex = next.vertex;
                int nextCost = curCost + next.cost;
                
                // 더 짧은 경로를 찾으면 갱신
                if (nextCost < cost[nextVertex]) {
                    cost[nextVertex] = nextCost;
                    pq.offer(new Node(nextVertex, nextCost));
                }
            }
        }
        
        return cost;
    }
}

Footnotes

  1. [되기] 코딩 테스트 합격자 되기 - 자바 편(~189 스택까지), https://wikidocs.net/232020, 2024.03.04 09:45 ↩

백링크