프로그래머스 (Summer/Winter Conding ~2018) | LV.2 배달 - 다익스트라 문풀 (Java)

⬛ 프로그래머스 | LV.2 배달 - 다익스트라 문풀 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

문제 설명

---

💚문제 접근 방식

문제를 읽으면서 다익스트라 문제라고 판단했다.

시작점은 1번 정점으로 항상 고정되어 있고, 다른 모든 정점으로의 최단거리로 배달했을 때 그 거리가 K이하인 경우 배달 가능으로 판단하여 개수를 리턴하라는 문제이다.

1) Edge 클래스, distance[] 배열, graph 리스트를 선언했다.

2) road 2차원 배열을 순회하면서 graph에 양방향 간선을 세팅해줬다.

3) 다익스트라를 호출한다.

• distance는 N+1까지 MAX값으로 초기화
• pQ 선언하여 초기값 담고, distance[s] = 0 세팅해준다.
• while로 pQ 빌 때까지 순회하면서 매번 현재 좌표를 경유한 거리가 기존의 nx distance값보다 작을 때마다 갱신하고 pQ에 담아주면서 순회를 한다.
• 이후 더 이상 갱신할 최소거리가 없을 때 while을 탈출한다.
• for문으로 distance 순회하면서 k이하 거리를 갖는 애들을 ++처리하여 반환해준다.

4) 반환한 값이 최종 정답이 된다.

 

💚 제출 코드

import java.util.*;
class Edge implements Comparable<Edge>{
    int e, v;
    Edge(int e, int v){
        this.e = e;
        this.v =v;
    }
    public int compareTo(Edge o){
        return this.v- o.v;
    }
}
class Solution {
    static int[] distance;
    static List<List<Edge>> graph;
    //다익스트라 함수
    public static int dijkstra(int s, int k){
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[s] = 0;
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.offer(new Edge(s, 0));
        
        while(!pQ.isEmpty()){
            Edge cur = pQ.poll();
            if(cur.v > distance[cur.e]) continue;
            
            for(Edge nx : graph.get(cur.e)){
                if(distance[nx.e] > distance[cur.e] + nx.v){
                    distance[nx.e] = distance[cur.e] + nx.v;
                    pQ.offer(new Edge(nx.e, distance[nx.e]));
                }
            }
        }
        
        int ans = 0;
        for(int i=1; i<distance.length; i++){
            if(distance[i] > k) ans++; 
        }
        return distance.length-1-ans;
    }
    
    //솔루션 함수 
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        graph = new ArrayList<>();
        for(int i=0; i<=N; i++){
            graph.add(new ArrayList<>());
        }
        distance = new int[N+1];
        
        for(int[] x :road){
            //양방향 간선
            int a = x[0];
            int b = x[1];
            int v = x[2];
            graph.get(a).add(new Edge(b, v));
            graph.get(b).add(new Edge(a, v));
        }
        
        answer = dijkstra(1, K);

        return answer;
    }
}