[JAVA] Programmers : 배달

문제

코딩테스트 연습 - 배달

 

해결방법

N개의 마을이 있고 각 마을을 잇는 도로가 있다.

해당 도로를 건너는데 시간은 도로마다 다르다.

 

이때 1번 마을에서 각 마을에 배달을 하려고 하는데 K 시간 이하인 곳만 배달이 가능해서 배달 가능한 마을의 수를 구하는 문제이다.

 

문제를 보자마자 다익스트라가 떠올라서 다익스트라를 이용해서 풀이를 했다.

 

각 마을의 도로의 정보는 인접 리스트를 이용해서 정리하고,

다익스트라 배열을 마을 개수만큼 생성한 다음 문제에서 나올 수 있는 최댓값으로 초기화해두고(귀찮아서 int 최댓값을 사용하긴 하였다) 시작점에서 부터 탐색을 시작한다.

 

시작점부터 탐색하면서 다음 마을까지 가는 시간이 현재 다익스트라 배열에 저장된 값보다 작으면 값을 바꾸고 이동시킨다.

 

모든 탐색이 종료된 후에 다익스트라 배열에서 K이하인 값을 찾아 출력하였다.

 

코드

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        // 인접 리스트
        ArrayList<Node> list[] = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();
        
        for (int i = 0; i < road.length; i++) {
            int cur = road[i][0];
            int next = road[i][1];
            int time = road[i][2];
            
            list[cur].add(new Node(next, time));
            list[next].add(new Node(cur, time));
        }
        
        // 다익스트라 시작
        int[] town = new int[N + 1];
        Arrays.fill(town, Integer.MAX_VALUE);
        town[1] = 0;
        
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(1, 0));
        
        while (!q.isEmpty()) {
            Node node = q.poll();
            
            for (int i = 0; i < list[node.next].size(); i++) {
                int next = list[node.next].get(i).next;
                int time = list[node.next].get(i).time;
                
                if (town[next] > node.time + time) {
                    town[next] = node.time + time;
                    q.add(new Node(next, town[next]));
                }
            }
        }
        
        // 배달 가능한 곳 찾기
        for (int i : town) {
            if (i <= K) answer++;
        }

        return answer;
    }
}

class Node implements Comparable<Node> {
    int next;
    int time;
    
    Node (int next, int time) {
        this.next = next;
        this.time = time;
    }
    
    @Override
    public int compareTo(Node o) {
        return time - o.time;
    }
}