9 - 1. Dijkstra 예제 (Parity Constraint Shortest Path)

백준 20128번: Parity Constraint Shortest Path

20128번: Parity Constraint Shortest Path

 

풀고 나면 꽤나 쉬운 문제인데.. 방법을 적용하기 위해 증명을 생각하기 조금 어려웠던 문제입니다.

제목을 대충 해석하면 뭔 최단 경로입니다. ㅎㅎ

 

대략적인 문제 내용을 요약하자면 아래와 같습니다.

1. 1번부터 N번까지 모든 노드의 최단 경로를 구하는 문제입니다.
2. 임의의 두 노드 사이에 존재하는 간선은 단 하나
3. 양방향 노드로 구성되며, 노드수: 10만, 간선 수: 30만
4. 단, 어떤 i번 노드까지 최단 경로를 구하되 최단 거리의 합이 홀수인 경우와 짝수인 경우를 모두 구합니다.
5. 만약 해당 경로가 존재하지 않는다면, -1을 출력합니다.

위의 내용을 기반으로 그려본 예시 그래프와 결과입니다.

그림 1. 예시 그래프 및 결과

 

 

문제 내용은 파악이 됐는데, 최단 경로라고 무조건 다익스트라를 적용하시면 안 됩니다.

 

다익스트라의 조건이 맞는지 확인해야죠.

• 우선 간선에 음수 가중치가 들어오면 안 됩니다.
• 최단 경로의 부분 경로도 최단 경로인지 확인합니다.
• 시간 복잡도 O(ElogV)로 제한 시간 안에 동작시킬 수 있는지 확인합니다.

위의 조건들은 다 만족하는 듯합니다만, 문제가 있습니다.

바로 홀수, 짝수의 최단 경로 모두 구해야 하는 점이죠.

만약, 최단 경로가 짝수였다면, 이후 다른 값은 접근하지 못하는데 일반적인 코드론 두 경우 모두를 구할 순 없겠죠.

홀수도 마찬가지입니다.

 

우선 어떤 수들의 합을 한 경우 홀수와 짝수가 나오는 조건에 대해 정리해봅시다.

짝 + 짝 = 짝

홀 + 짝 = 홀

홀 + 홀 = 짝

 

-> 홀수가 홀수 개면 수의 합은 홀수, 홀수가 짝수 개면 수의 합은 짝수입니다.

따라서, 홀수와 짝수의 개수를 미리 쭉 저장해주면 좋을 것 같다는 생각이 첫 번째로 떠오릅니다.

 

하지만, 이를 배열로 표현하긴 어렵겠죠.

왜냐하면, 다음 노드의 번호와 홀수 짝수의 개수를 세려면 2차원으로 구성해야 하는데 최악 10만 * 10만이니까요.

그럼 그냥 현재까지 최소비용을 합한 값을 2로 나눈 나머지로 표현하면 될 것 같습니다.

우린 각 경로별 값은 배열의 값으로 저장할 테고 탐색을 진행할 땐 홀/짝 여부만 알면 되니까요.

 

배열로 표현하면 long [][] dist = new long [2][N] 이런 식으로 표현 가능하겠습니다.

0이면 짝수, 1이면 홀수로 잡으면 됩니다. (∵ 홀 % 2 == 1, 짝 % 2 == 0)

이제 구현을 해보기 전, 우리가 생각한 방식이 맞는지 확인해야 합니다.

홀/짝으로 나누어 계산을 했는데, 올바른 최소 비용을 구할 수 없다면 다익스트라로 푸는 문제가 아니니까요.

 

앞선 포스트에서 최단경로의 부분 경로는 최단경로라는 것을 우리는 공부했습니다.

이 정의에 따라 부분 최단경로를 이용해 1개의 최단 경로는 구할 수 있습니다.

즉, 어떤 최단 경로 S가 짝수/홀수인 경우 나머지 홀수/짝수인 최단 경로를 구할 수 있느냐가 핵심이죠.

 

따라서, 목적지 노드의 짝수 최소 경로와 홀수 최소 경로가 독립적이라는 것을 확인해봅시다.

두 경로가 독립적이라면 둘에 대한 결과를 각각 구할 수 있겠죠.

 

그림 2. 독립적 결과 확인 그래프

 

예를 들어 해당 그래프에서 A -> C -> B가 홀수 최단 경로라고 가정하겠습니다.

최종 목적지 B까지 가는데 C에서 다른 노드를 거치지 않고, 짝수 최단 경로를 만들어 낼 수 있을까요?

불가능합니다.

 

C까지 최소 비용이 짝수인 경우

C + 비용(CB) = 홀수이며, 따라서 간선 CB의 비용은 무조건 홀수입니다.

C까지 최소 비용이 홀수인 경우 

C + 비용(CB) = 홀수이며, 따라서 간선 CB의 비용은 무조건 짝수입니다.

 

임의의 최단 경로 C까지의 홀/짝 여부가 변경될 때마다, 간선 비용도 그 여부가 바뀝니다.

따라서 서로에게 영향을 미칠 수 없습니다. 물론 CB 간선이 여러 개라면 독립적이진 못합니다.

물론 결괏값 자체는 이전 경로 C까지 비용에 종속적이겠죠.

즉, 문제의 조건 '임의의 노드 두 개 사이엔 최대 한 개의 간선이 존재한다.'에 따라 만들 수 없죠.

각 부분별 홀/짝 최단 경로가 서로 독립적입니다.

결국 목적지 노드 (B)까지 최소 짝수 비용이 갱신돼도 B까지 최소 홀수 경로를 구할 수 있습니다.

반대도 마찬가지겠죠.

 

정리해 보면 홀/짝 여부와 어떤 노드와의 관계는 독립적인데, 우리는 이러한 경우를 항상 배열의 차원을 늘려 계산했습니다.

예를 들어, 어떤 지도를 2차원 배열로 구성해 BFS탐색을 하는 경우 row와 col로 지정된 칸이 모두 서로 독립적이므로 사용합니다.

 

그리고 다익스트라 동작 방식에 따라 최종적으로 도달하지 못하는 노드는 만족하는 경로가 당연히 없습니다.

만족하는 경로가 있다면 완전 탐색처럼 진행을 해서라도 도달할 테니까요.

또한 도달 못하는 경로는 최댓값으로 고정되어있을 테니 최댓값을 가지는 배열은 -1로 출력해주면 됩니다.

 

 

아래는 정리한 내용들을 토대로 구성한 코드입니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static final long INF = 1_000_000_000_000_000L;
    private static final String SPACE = " ";
    private static final String NEW_LINE = "\n";

    private static ArrayList<Node>[] path;
    private static long[][] dist;

    private static class Node implements Comparable<Node>{
        int node;
        int count;
        long cost;

        public Node(int node, int count, long cost) {
            this.node = node;
            this.count = count;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node n) {
            return this.cost < n.cost ? -1: 1;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        path = new ArrayList[N];
        dist = new long[2][N];
        for(int i = 0; i < N; i++) {
            path[i] = new ArrayList<>();
            dist[0][i] = dist[1][i] = INF;
        }

        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken()) - 1;
            int node2 = Integer.parseInt(st.nextToken()) - 1;
            long cost = Long.parseLong(st.nextToken());

            path[node1].add(new Node(node2, 0, cost));
            path[node2].add(new Node(node1, 0, cost));
        }

        System.out.println(dijkstra(N));
    }

    private static String dijkstra(int n) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0, 0L));

        dist[0][0] = 0;

        while(!pq.isEmpty()) {
            Node current = pq.poll();
            if (current.cost > dist[current.count][current.node]) continue;

            for(Node next: path[current.node]) {
                long cost = next.cost + dist[current.count][current.node];
                int nextCount = (int) (cost % 2);

                if(dist[nextCount][next.node] <= cost) continue;
                dist[nextCount][next.node] = cost;

                pq.offer(new Node(next.node, nextCount, dist[nextCount][next.node]));
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(dist[1][i] == INF ? -1: dist[1][i]).append(SPACE)
                    .append(dist[0][i] == INF ? -1: dist[0][i]).append(NEW_LINE);
        }

        return sb.toString();
    }
}

 

 

최댓값을 1,000,000,000,000,000으로 잡아준 이유는 입력으로 최대 10억이 들어오기 때문입니다.

10억 * (노드 수 or 간선 수)를 해도 벗어나지 않을 만큼 큰 값을 최댓값으로 해서 갱신되도록 해야겠죠.

 

또한 이전 포스팅에서 보지 못한 코드가 보입니다.

if (current.cost > dist [current.count][current.node]) continue

해당 코드는 DP의 개념과 유사하게 생각하시면 됩니다.

노드와 간선수가 많고, 따라서 반복적인 연산이 많은 테스트 케이스가 들어올 가능성이 높은 경우 사용합니다.

생각보다 해당 코드 없이 시간 초과 나는 문제가 꽤 많습니다.

해석해보면, 현재 지나갈 간선의 비용이 현 노드까지 도달한 비용보다 크다는 뜻입니다.

 

 

글로 표현하면 약간 헷갈릴 수 있으니 그림으로 표현하겠습니다.

그림 3. current.cost > dist[current.count][current.node] 설명

 

이렇게 노드가 존재할 때 prev 노드에 대한 최소 비용이 갱신되는 과정을 상상해 봅시다.

dist [current.count][current.node] > dist [prev.count][prev.node] + current.cost 인 경우 PQ에 담기겠죠.

 

이후 PQ에서 뽑아진 dist [current.count][current.node]가 current.cost가 됩니다.

즉, 어떤 current.cost가 나왔을 때, 이미 dist [current.count][current.node]가 더 작아졌을 수 있습니다.

PQ에는 많은 결과 값들이 존재하고 있으니까요.

 

중간에 변경된 수치로 인해 이미 current.cost는 탐색하지 않아도 되는 값이 되어버립니다.

그림 4. current.cost > dist[current.count][current.node] 설명

1, 2, 3 간선을 계산한 결과 모두 PQ에 존재하며 비용은 1 < 2 < 3인 경우가 바로 그것입니다.

뭐.. 결국 이것도 다익스트라 개념에서 봤던 모습이긴 합니다.

재귀 DP를 해보신 분들은 아시겠지만, 이미 갱신된 값은 그 값을 리턴하죠.

그렇게 이해하셔도 좋을 것 같습니다. 어쨌든 위의 조건문으로 상당히 많은 경우의 수를 걸러낼 수 있습니다.

 

시간 복잡도는 O(ElogV) = 30만 * 약 70 = 2100만 정도인데, 코너 케이스가 상당히 많은 듯합니다.

문제를 접근하는 방법과 current.cost를 이용해 경우의 수를 걸러내는 것 모두 잘 이해하고 넘어가시길 바랍니다.

경우의 수 걸러내지 않으면 시간 초과를 받습니다. ㅎㅎ

 

 

증명을 해보려 했는데, 이해가 잘 되실진 모르겠습니다.

증명이 내용적으로 부족할 수 있어 좀 더 고민해볼 참이지만, 첨언해주시면 관련해서 고민해보겠습니다.

또한, 다른 부분에도 질문이나 의문 사항 남겨주시면 피드백하겠습니다. 감사합니다.