871. Minimum Number of Refueling Stops - Streak 19

현재 노드에 도달할 때까지 가장 적은 주유 횟수가 유리하다.
같은 주유 횟수라면, 더 많은 연료를 가지고 있는 쪽이 유리하다.

 

 

그렇다면 가능한 주유 횟수를 1회씩 증가시키면서 최대 인덱스까지 도달 가능 여부를 검사하면 가장 먼저 끝에 도달하는 순간의 주유횟수가 최대가 될 것이다.

 

주유소는 최대 500개까지 있으니 주유 가능 횟수도 최대 500회이고, 따라서 500회 순회하면서 확인하면 1초 내에 가능할 듯 하다.

 

 

대략적인 수도 알고리즘을 설계해보자.

1. 이전 인덱스에서 현재 인덱스에 도달 가능한지 확인한다.
   1. 도달 불가능하면 반복문을 종료한다.
2. 과거 인덱스에서 주유를 하지 않고, 현재 인덱스에서 주유를 하는 것이 더 멀리 갈 수 있는지, 과거 인덱스에서 주유를 하고 현재 인덱스에서 주유를 하지 않는 것이 더 멀리 갈 수 있는지 비교한다.
   1. 둘 중 더 나은 쪽을 현재까지 주유를 1회 수행한 경우의 남은 기름으로 저장해둔다.
3. 반복문이 끝나면, 주유를 1회 수행한 경우의 남은 기름을 주유를 0회 수행한 경우의 남은 기름에 복사한다.

이 방식은 "같은 곳에서 여러번 주유"라는 불가능한 상황의 발생 가능성이 존재한다.
따라서, 이전에 주유했던 정보를 알고 있어야 중복 주유를 막을 수 있다.

 

이렇게 되면 노드가 500*500 개가 필요해지지만, 시/공간복잡도 상으로 문제는 없다.

더 효율적인 방법이 없을까?

 

덱을 이용한 0-1 BFS로 문제를 풀 순 없을까? 라는 아이디어가 떠올랐다.
만약 이번 칸에서 주유를 안한다면 앞에 추가하고, 주유를 한다면 뒤에 추가한다.
이 방식으로 가장 빨리 도달하는 경우를 탐색하는 것 또한 가능하다.
하지만 이 경우 남은 연료를 계산하기가 까다롭다.

 

이 점을 해결하려면 다익스트라 형태로 남은 연료를 계속해서 구해야 한다.
그 경우 다음 인덱스에 도달하기 위해 주유를 한번 더 한 방문이 소실될 위험이 존재한다.
따라서 이 경우도 문제가 해결되지 않는다.

 

아니면, 주유 1당 1칸씩 이동할 수 있다는 정보를 이용할 수 없을까?

맨 처음 생각했던 주유 횟수 증가 방식의 탐색은 어떨까?

그 경우, 중복 주유를 막는 방식이 필요한데,
지금까지 지난 주유소를 최대 힙으로 저장해둘 수 있다.
이러면 중복 주유를 막고 한번만 주유해줄 수 있다.

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int n = stations.length + 2;
        PriorityQueue<Long> pq = new PriorityQueue(Collections.reverseOrder());
        int nowPos = 0;
        long nowFuel = startFuel;
        int refuelCnt = 0;
        while(nowPos < stations.length && stations[nowPos][0] <= nowFuel)
            pq.add((long)stations[nowPos++][1]);
        while(nowFuel < target){
            refuelCnt++;
            if(pq.isEmpty()) return -1;
            nowFuel += pq.poll();
            while(nowPos < stations.length && stations[nowPos][0] <= nowFuel)
                pq.add((long)stations[nowPos++][1]);
        }
        return refuelCnt;
    }
}