[프로그래머스] 배달

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

1번 마을에서 각 마을까지의 최단거리를 구하고 그 최단거리가 K보다 작은 곳의 수를 알아내면 되는 문제이다.

 

해당 그래프는 가중치가 있는 그래프이기 때문에 최단거리를 구할 때 다익스트라 알고리즘을 통해 구할 수 있다.

바로 코드를 보자.

3. 내 코드

---

import java.util.*;
class Solution {
    class Node {
        int dest;
        int weight;
        
        Node(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
    class Graph{
        int N; 
        List<Node>[] graph;
        
        Graph(int n) {
            this.N = n + 1;
            graph = new ArrayList[n + 1];
            
            for(int i = 0; i < n + 1; i++) {
                graph[i] = new ArrayList<Node>();
            }
        }
        
        void addEdge(int start, int end, int weight) {
            graph[start].add(new Node(end, weight));
            graph[end].add(new Node(start, weight));
        }
        
        private int[] dijkstra() {
            PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.weight, o2.weight));
            int[] distance = new int[N + 1];
            Arrays.fill(distance, Integer.MAX_VALUE);

            queue.add(new Node(1, 0)); 
            distance[1] = 0;

            while(!queue.isEmpty()) {
                int cur_node = queue.poll().dest;

                List<Node> adj = graph[cur_node];
                for(Node n: adj) {
                    int adj_node = n.dest;
                    int weight = n.weight;                                                                                                      
                    if(distance[adj_node] > distance[cur_node] + weight) {
                        distance[adj_node] = distance[cur_node] + weight;
                        queue.add(new Node(adj_node, weight));
                    }
                }
            }

            return distance;
        }
    }
    
    public int solution(int N, int[][] road, int K) {
        
        // 1. 그래프 만들기
        Graph graph = new Graph(N);
        for(int i = 0; i < road.length; i++) {
            int[] node_info = road[i];
            graph.addEdge(node_info[0], node_info[1], node_info[2]);
        }
        
        // 2. 다익스트라 알고리즘 실행
        int[] distance = graph.dijkstra();
        
        // 3. K이하로 갈 수 있는 마을 개수 세기
        int count = 0;
        for(int i = 1; i < distance.length; i++) {
            if(distance[i] <= K) 
                count++;
        }
        
        return count;
    }
    
}

시간 복잡도

• O(ElogV)

 

4. 피드백

---

• 간선이 있는 그래프에서 최단거리를 구할 땐 다익스트라 알고리즘