[알고리즘] 다익스트라 변형 (Dijkstra)

다익스트라 알고리즘에 대한 내용은
[알고리즘] 다익스트라 이론과 우선순위 큐로 최적화 하기 (Dijkstra)를 참고해 주세요.

일반적인 다익스트라 알고리즘에서는 int[] d 배열을 통해 특정 정점까지의 최단 거리를 탐욕적으로 선택한다. 하지만 문제에서 변형이 들어가면 1차원 배열로는 부족할 수도 있다.

상태가 추가된 다익스트라

백준 16118 - 달빛 여우 문제를 예시로 보면, 여우의 경우 일반적인 다익스트라지만,
늑대의 경우 길을 건널때 마다 속도가 두배가 되거나 절반이 된다.

이럴 경우, 단순히 가중치를 d배열에 넣으면, 그 값이 최선이 아닐 수도 있다.

예를 들어, d[3] = 7인 상태이고, 알고리즘을 돌리는 중에 d[3]을 도달하는 비용이 9가 나왔을 때, 원래 다익스트라 알고리즘이면 넘어가겠지만, 사실은 원래 저장된 값은 직전에 빠르게 달렸던 것이였고, 새로운 9 값은 이제 빠르게 달릴 차례였을 수도 있다. 그러면 d[3] = 7 값은 확정할 수 없다.

해법은 d 배열을 2차원으로 만드는 것이다.

d 배열을 단순히 정점에 대한 최단 거리가 아니라
정점에 대한 특정 상태에서의 최단 거리를 저장하면 된다. 그러면 상태 별로 각각 탐욕적으로 선택할 수 있게 된다.

// d[i][j] = i 정점에서 j 상태일 때 최단거리
int[][] d = new int[n + 1][2];

코드

아래는 16118번 문제의 늑대 전용 다익스트라 함수이다.

class WolfState {
    int node;
    int totalDist;
    int isFast;

    WolfState(int node, int totalDist, int isFast) {
        this.node = node;
        this.totalDist = totalDist;
        this.isFast = isFast;
    }
}

static int[] wolfDijkstra(int start) {
    // d[i][j] 에서 j 가 0이면 다음번에 느리게 이동, 1은 다음번에 빠르게
    int[][] d = new int[n + 1][2];
    for (int i = 0; i <= n; i++) {
        Arrays.fill(d[i], Integer.MAX_VALUE);
    }
    PriorityQueue<WolfState> pq = new PriorityQueue<>((s1, s2) -> Integer.compare(s1.totalDist, s2.totalDist));

	// 처음 시작 시 빠르게 달려야 하므로 isFast 에 1 넣음
    pq.offer(new WolfState(start, 0, 1));
    
    // d 배열 초기화. 주의점은 d[start][0] = 0 으로 초기화 하면 안된다.
    d[start][1] = 0;

    while (!pq.isEmpty()) {
        WolfState cur = pq.poll();

		// 정점에서의 현재 상태만 검사
        if (cur.totalDist > d[cur.node][cur.isFast]) {
            continue;
        }

        for (Node next : graph.get(cur.node)) {
        	// 부동소수점 연산을 피하기 위해 속도 절반과 두배가 아닌, 1배와 4배로 풀었다.
            int nextDist = cur.totalDist + (cur.isFast == 1 ? next.weight : next.weight * 4);

            int toggleState = cur.isFast == 1 ? 0 : 1;
            if (d[next.to][toggleState] > nextDist) {
                d[next.to][toggleState] = nextDist;
                pq.offer(new WolfState(next.to, nextDist, toggleState));
            }
        }
    }

	// 두 상태중에 최소값만 반환
    int[] dist = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        dist[i] = Math.min(d[i][0], d[i][1]);
    }

    return dist;
}

d[start][0] = 0으로 초기화하면 안 되는 이유는 다음과 같은 입력에서 확인할 수 있다.

5 5
1 2 1
1 4 5
1 5 3
4 5 4
2 3 400

이 경우, 정답은 0이어야 하는데 1이 나오는 오류가 발생한다. 원점으로 0 상태로 다시 방문하는 경우가 최선일 수도 있기 때문이다. (참고)