프로그래머스 Lv.3) 배달

배달

코딩테스트 연습 - 배달

풀이

문제를 보고 많은 생각이 스쳐 지나갔다. MST가 먼저 떠올랐는데, 모든 경로를 잇는 것이 중요한 문제가 아니기 때문에 아니라고 생각했다. 다음은, 최단 거리 알고리즘이었다. 다익스트라(dijkstra) 이름이 기억나지 않았지만, 이 로직이 떠올랐다.

 

하지만, 처음에 풀었을 때는 edge를 따로 저장하지 않고, 주어진 road만 돌면서 우선순위 큐에 저장하고 최소 비용으로 잘 잇는다면 가능하지 않을까 싶었다. 결과는 40점, 더 앞선 길 중 최저 비용으로 저장을 해준다해도, 뒤의 길들이 더 적은 비용이 들어도 앞선 길들에 대해 최소 비용을 저장하지 못한다는 점이 있었다. 그래서 그냥 edge에 먼저 저장한 뒤에, 다익스트라를 적용하는 방법을 사용했다.

 

로직

1. 기준점 1에서 N까지 갈 때, 최소 비용을 저장하는 costArr 1차원 배열을 만든다.

2. 주어진 road를 돌면서 각 도로에 대해 최소 비용이 드는 edge를 생성한다.

3. 도시와 이동 비용을 저장하는 Road 클래스를 만들어, 이동 비용에 따라 오름차순으로 Road가 저장될 수 있는 우선순위 큐를 만든다.

4. 시작 도시인 1과 자기 구역에 배달이 가능하기 때문에 비용 0을 Road형 변수를 통해 우선순위큐에 저장한다. 

5. 1부터 edge에 연결되어 있는 도시를 탐색하면서, 1에서 해당 도시까지 드는 비용과 다른 연결된 도시들을 통해 도착하는 비용을 비교한다. (costArr 과 costArr[route.city] + edge[route.city][i] 비교 부분)

6. 경유해서 가는게 더 빠른 경우, 해당 도시와 드는 비용을 담는 Road 변수를 만들어 우선순위 큐에 저장한다.

7. 모든 큐를 소모하면서 저장된 CostArr에서 1에서 각 도시까지 가는데 드는 최소 비용이 주어진 K 이하인 경우를 카운트한다.

 

 

코드

import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    final int ROOT = 1, MAX = 500001;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[] costArr = inItCost(N);
        int[][] edge = getEdge(road, N);
        return getAnswer(costArr, edge, N, K);
    }
    
    private int[] inItCost(int n) {
        int[] result = new int[n+1];
        Arrays.fill(result,MAX);
        result[1] = 0;
        return result;
    }
    
    private int[][] getEdge(int[][] road, int n) {
        int[][] result = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
            Arrays.fill(result[i], MAX);
        }
        for(int[] route : road) {
            int cost = Math.min(result[route[0]][route[1]], route[2]);
            result[route[0]][route[1]] = result[route[1]][route[0]] = cost;
        }
        return result;
    }
    
    private int[] dijkstra(int[] costArr, int[][] edge, int N) {
        PriorityQueue<Road> roadQ = new PriorityQueue<>();
        roadQ.offer(new Road(1,0));
        
        while(!roadQ.isEmpty()) {
            Road route = roadQ.poll();
            for(int i=1; i<=N; i++) {
                if(edge[route.city][i] != MAX) {    // city랑 연결된 곳
                    if(costArr[i] > costArr[route.city] + edge[route.city][i]) {
                        costArr[i] = costArr[route.city] + edge[route.city][i];
                        roadQ.offer(new Road(i, costArr[i]));
                    }
                }
            }
        }
        return costArr;
    }
    private int getAnswer(int[] costArr, int[][] edge, int N, int K) {
        costArr = dijkstra(costArr, edge, N);
        int result =0;
        for(int i=1; i<=N; i++) {
            if(costArr[i] <=K) {
                result++;
            }
        }
        return result;
    }
}

class Road implements Comparable<Road>{
    int city;
    int cost;
    
    public Road(int city, int cost) {
        this.city = city;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Road r) {
        return this.cost > r.cost ? 1:-1;
    }
}