[알고리즘] 프로그래머스 배달 -최단경로, 다익스트라- 자바Summer/Winter Coding(~2018)

 

 

 

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

 

프로그래머스 LV2 배달 문제를 풀어봤습니다. ㅎㅎ

1번 마을에서 K 이하의 시간으로 배달을 갈 수 있는 마을의 개수를 구하는 문제입니다.

 

그래서 1번 마을에서 각 마을간의 최단경로(최단시간)를 구해서 K시간 이하가 몇개 있는지 답을 구하면 됩니다. 

 

다익스트라가 사용되며 도시의 개수는 N개 그리고 한 도시의 주변 개수는 road.length  이므로 각각 정점개수(V), 간선개수(E)라 칭하면 시간복잡도는 보통 O(|E||log|V|) 가 됩니다. (문제에서도 보다시피 road의 길이 즉 간선이 도시의 개수(정점)보다 많을 경우가 대부분이기 때문에)

 

 

풀이는 다음과 같습니다.

 

[Java]

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

class Solution {
    private static ArrayList<Edge>[] edgeList; // 도시 인접리스트
    private static int[] distance; // 1번 도시와 다른 도시간의 최단 경로

    private static void dijkstra() {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        queue.add(new Edge(1, 0));
        while (!queue.isEmpty()) {
            Edge edge = queue.poll();
            int vertex = edge.vertex;
            int weight = edge.weight;
            if (distance[vertex] < weight) {
                continue;
            }
            for (int i = 0; i < edgeList[vertex].size(); i++) { // 해당 도시와 연결되 있는 도시들 탐색
                int vertex2 = edgeList[vertex].get(i).vertex;
                int weight2 = edgeList[vertex].get(i).weight + weight;
                if (distance[vertex2] > weight2) { // 최단경로 세팅
                    distance[vertex2] = weight2;
                    queue.add(new Edge(vertex2, weight2));
                }
            }
        }
    }


    public int solution(int N, int[][] road, int K) { // N : 마을의 개수, road : 마을번호와 비용, K : 최대 가능한 비용
        int answer = 0;
        //초기화 과정
        edgeList = new ArrayList[N + 1];
        distance = new int[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        for (int i = 1; i <= N; i++) {
            edgeList[i] = new ArrayList<>();
        }
        for (int i = 0; i < road.length; i++) {
            edgeList[road[i][0]].add(new Edge(road[i][1], road[i][2]));
            edgeList[road[i][1]].add(new Edge(road[i][0], road[i][2]));
        }
        distance[1] = 0; //1번 도시 - 자신 최단 경로 0
        //다익스트라
        dijkstra();
        // 1번마을에서 K 이하 비용인 도시 개수 구하기
        for (int cost : distance) {
            if (cost <= K) {
                answer++;
            }
        }
        return answer;
    }

    private static class Edge implements Comparable<Edge> {
        int vertex; //
        int weight; //배달주문 시간

        public Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!