[프로그래머스] 배달

작성일: 2024-11-24

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12978

접근 방식

다익스트라 알고리즘을 활용해야 한다.

다익스트라 알고리즘이란?
특정 노드까지의 최단 거리를 구하는 알고리즘을 말한다.
DP를 그래프에 연결한다고 생각하면 편하다.

다익스트라 알고리즘을 통해 각 마을까지의 최단 배달 시간을 구해서

배달이 가능한 마을만 세면 된다.

잘못된 접근

import java.util.*;

class Solution {
    class Node{
        int target;
        int dist;
        Node(int target, int dist){
            this.target=target;
            this.dist=dist;
        }
    }
    public int solution(int N, int[][] road, int K) {
        // 마을 1개면 바로 리턴
        if(N==1) return 1;

        int answer = 0;
        LinkedList<Node> list[] = new LinkedList[N+1];

        // 리스트 초기화
        for(int i=1; i<=N; i++){
            list[i] = new LinkedList();
        }

        // 마을 양방향 연결 및 거리 저장
        for(int[] r:road){
            list[r[0]].add(new Node(r[1], r[2]));
            list[r[1]].add(new Node(r[0], r[2]));
        }

        // 배달
        int[] dist = delivery(N, list, K);
        for(int i=1; i<=N; i++){
            answer = dist[i]<=K ? answer+1 : answer;
        }

        return answer;
    }

    // 배달 가기
    int[] delivery(int N, LinkedList<Node> list[], int distance){
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist); // 내림차순 정렬
        int dist[] = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 최단 거리를 구하기 위해 미리 채우기

        // 1번 마을에서 출발
        pq.offer(new Node(1, 0));

        // 나머지 마을들 방문
        while(!pq.isEmpty()){
            Node cur = pq.poll();

            for(Node n:list[cur.target]){
                // 내가 다음에 가야할 마을까지의 거리 계산
                int next = dist[cur.target] + n.dist;
                if(next>distance) continue;
                // 만약 내가 다음에 방문해야 할 마을까지의 거리가 기존 해당 마을까지의 거리보다 짧다면 (가깝다면)
                if(next < dist[n.target]){
                    dist[n.target] = next; // 해당 마을까지의 거리 변경
                    pq.offer(n); // 그 마을 가자
                }
            }
        }
        return dist;
    }
}

계속 문제를 찾아봐도 정답이 아닌 이유를 알 수 없었는데, 그렇게 gpt에 물어보려던 찰나에 아주 미세한 실수를 발견했다.

바로.

1번 마을에서 출발할 때의 거리를 초기화해주지 않은 것..

거리 배열을 초기화하는 과정에서, 모든 마을까지 도착 시간을 모두 Integer.MAX_VALUE로 설정했기 때문에, Integer의 최댓값을 초과한 결과값이 나와 원하는 결과를 만들어 낼 수 없다.

실제로 next의 값을 찍어보면

2:-2147483648
4:-2147483647
1:-2147483647
3:-2147483645
5:-2147483646

위와 같이 해당 마을까지의 거리가 음수로 변경되어, 모든 마을의 방문할 수 있는 것으로 나온다.

따라서 1번 마을을 꼭 초기화해주어야 한다. (방문 처리와 동일)

결과

소스 코드

import java.util.*;

class Solution {
    class Node{
        int target;
        int dist;
        Node(int target, int dist){
            this.target=target;
            this.dist=dist;
        }
    }
    public int solution(int N, int[][] road, int K) {
        // 마을 1개면 바로 리턴
        if(N==1) return 1;

        int answer = 0;
        LinkedList<Node> list[] = new LinkedList[N+1];

        // 리스트 초기화
        for(int i=1; i<=N; i++){
            list[i] = new LinkedList();
        }

        // 마을 양방향 연결 및 거리 저장
        for(int[] r:road){
            list[r[0]].add(new Node(r[1], r[2]));
            list[r[1]].add(new Node(r[0], r[2]));
        }

        // 배달
        int[] dist = delivery(N, list, K);
        for(int i=1; i<=N; i++){
            answer = dist[i]<=K ? answer+1 : answer;
        }

        return answer;
    }

    // 배달 가기
    int[] delivery(int N, LinkedList<Node> list[], int distance){
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist); // 내림차순 정렬
        int dist[] = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 최단 거리를 구하기 위해 미리 채우기

        // 1번 마을에서 출발
        pq.offer(new Node(1, 0));
        dist[1] = 0;
        // 나머지 마을들 방문
        while(!pq.isEmpty()){
            Node cur = pq.poll();

            for(Node n:list[cur.target]){
                // 내가 다음에 가야할 마을까지의 거리 계산
                int next = dist[cur.target] + n.dist;
                if(next>distance) continue;
                // 만약 내가 다음에 방문해야 할 마을까지의 거리가 기존 해당 마을까지의 거리보다 짧다면 (가깝다면)
                if(next < dist[n.target]){
                    dist[n.target] = next; // 해당 마을까지의 거리 변경
                    pq.offer(n); // 그 마을 가자
                }
            }
        }
        return dist;
    }
}