[프로그래머스] 배달

문제

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

프로그래머스

문제 분석

[제한사항]

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

그래프 정보가 주어지고 1번 부터 K 이하 시간 안에 배달이 가능한 노드의 개수를 구하는 문제이다.

 

문제 접근

그래프와 가중치가 주어졌기 때문에 다익스트라 알고리즘이 제일 먼저 떠올랐다.

문제를 더 읽어보니 기본적인 다익스트라 알고리즘 문제였다. 

1번 노드에서 갈 수 모든 노드로 갈 수 있는 최단 배달 시간을 구하고 그 중 배달 시간이 K 아하인 노드의 개수를 세면된다.

 

코드

import java.util.*;

import java.util.*;

class Solution {
    static final int INF = Integer.MAX_VALUE;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        Map<Integer, List<int[]>> graph = new HashMap<>();
        
        for(int[] info : road){
            graph.putIfAbsent(info[0], new ArrayList<int[]>());
            graph.get(info[0]).add(new int[]{info[1], info[2]});
            
            graph.putIfAbsent(info[1], new ArrayList<int[]>());
            graph.get(info[1]).add(new int[]{info[0], info[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int[] distance = new int[N+1];
        Arrays.fill(distance, INF);
        
        pq.add(new int[]{1, 0});
        distance[1] = 0;
        
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            
            if(distance[cur[0]] < cur[1]) continue;
            
            for(int[] next : graph.get(cur[0])){
                int nextNode = next[0];
                int nextDist = next[1] + cur[1];
                
                if(nextDist < distance[nextNode]){
                    pq.add(new int[]{nextNode, nextDist});
                    distance[nextNode] = nextDist;
                }
            }
        }
        
        for(int n : distance){
            if(n<=K) answer++;
        }
        return answer;
    }
}