[다익스트라] 프로그래머스 배달 (실패 분석 - 복습 부족)

접근

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

이 문제는 보자마자 다익스트라로 풀어야 하는 것을 알았습니다.
하지만 우선순위 큐에 대한 부분이 떠오르지 않았고
빙빙 돌다가 결국 복습하면서 풀게 되었습니다.

틀린 원인을 생각하면 복습이 부족했기 때문에 틀리게 되었습니다.

다익스트라 알고리즘 정리

제가 작성한 다익스트라 알고리즘 정리를 들어가 복습하였습니다.

다익스트라는 모든 비용이 양수여야 합니다.
음수인 경우에는 벨만포드 알고리즘으로 풀어여 합니다.

먼저 복습한 내용을 정리해 보려고 합니다.
다익스트라는 어떤 점을 시작으로 그 지점과 각 지점까지 가는 가장 짧은 지름길을 구하는 문제입니다.

따라서 보통 각 시작점이 문제에서 주어집니다.
위 프로그레머스 배달 문제에서는 1번 마을이 시작점이 되고 1번 마을에서 각 마을까지의 지름길을 구하면 됩니다.

여기서 지름길을 구하는 방법에 대해서 생각해봅시다.
1. 처음에 각 지름길의 길이를 최댓값으로 초기화 시킵니다.
2. 이제 1번 마을과 연결된 마을부터 시작합니다.

1번 마을과 연결된 2번과 3번 마을을 봅시다.
2번까지의 길이는 12,
3번까지의 길이는 4입니다.

여기서 우리가 지름길이라고 판단할 수 있는 것은 아무래도 12보다는 4입니다.
그래서 우선순위에서 12는 뒤로 밀리게 됩니다.

3. 이제 3번 마을에서 시작합니다.
   

3번 마을과 연결된 4번 마을을 봅시다.
4번 마을까지의 길이는 1-3-4 이므로 기존 값에 4번까지의 길이를 더해줍니다.

이제 우선순위 비교를 해보면
지름길이다라고 느낄 수 있는 것은 4까지의 길입니다.

4. 이제 4번 마을에서 시작합니다.
   

4번 마을과 연결돤 2번과 5번 마을을 봅시다.
2번까지의 즉 1-3-4-2로 가는 길이 더 지름길입니다.
5번까지는 기존 저장된 길이와 비교했을 때 지름길이므로 1-3-4-5가 지름길이 됩니다.

결국 마지막에

위 형태를 가지게 됩니다.

따라서 다익스트라는 몇 가지 방법을 기억해야 합니다.
1. 처음 초기화 작업 때는 지름길의 길이는 최대로 한다.
2. 우선순위를 매겨줄 수 있는 바구니가 필요하다.
3. 그 바구니에 넣을 때 규칙이 필요하다
4. 기존 지름길의 길이보다 작은 경우에 바구니에 넣는다.

풀이

import java.util.*;

class Solution {
    
    static ArrayList<ArrayList<Cost>> list;
    
    static class Cost{
        int node ;
        int cost ;
        public Cost(int node, int cost){
            this.node =node;
            this.cost=cost;
        }
    }
    
    static int[] timeRoad;
    static boolean[] visited;
    
    
    public int solution(int N, int[][] road, int K) {
        // 6시 30분~ 7시 10분
        int answer = 0;

        // 도로 양방향 통행
        // 1번 마을에서 시작 -> 각 마을에 음식 배달
        // N개의 마을 중에서 k시간 이하로 배달이 가능한 마을에서만 주문을 받는다.
        
        //마을의 수 N 1~50
        // road의 길이 1~2000
        // a : 시작 마을, b :끝나는 마을 , c: 길이
        // K 1~500_000
        
        timeRoad= new int[N+1];
        Arrays.fill(timeRoad,Integer.MAX_VALUE);
        
        visited = new boolean[N+1];
        list = new ArrayList<>();
        
        for(int i=0;i<=N;i++){
            list.add(new ArrayList<Cost>());
        }
        
        
        for(int i=0;i<road.length;i++){
            list.get(road[i][0]).add(new Cost(road[i][1],road[i][2]));
            list.get(road[i][1]).add(new Cost(road[i][0],road[i][2]));
        }
        
        make_time(1);
        

        for(int i=1;i<=N;i++){
            if(timeRoad[i]<=K) answer++;
        }
        
        
        return answer;
    }
    
    static void make_time(int start){
        
        PriorityQueue<Cost> q = new PriorityQueue<>((x1,x2)->{
            return x1.cost-x2.cost;
        });
        
        timeRoad[start]=0;
        q.offer(new Cost(start,0));
        
        while(!q.isEmpty()){
            Cost c = q.poll();
            
            if(c.cost>timeRoad[c.node]) continue;
            
            for(Cost next : list.get(c.node)){
                if( next.cost + c.cost < timeRoad[next.node]){
                    timeRoad[next.node]= next.cost + c.cost;
                    q.offer(new Cost(next.node,timeRoad[next.node]));
                }
            }
        }
    }   
             
    
}