TIL: 최소 이동 거리 계산 문제 풀이

문제 설명

ICPC는 지사 간의 메시지 전달 거리를 최소화하려고 한다.

• n: 교차로의 개수
• b: 지사의 수
• s: 하위 프로젝트 수
• r: 도로의 수

각 지사를 s개의 그룹으로 나누고 각 그룹이 하위 프로젝트를 맡는다.
이때, 월말에 메시지를 전달하는 데 필요한 운반원의 최소 이동 거리를 계산하는 문제이다.

문제 접근

1. 다익스트라 알고리즘:

   • 본부에서 각 지사까지의 최단 거리를 구하고,
   • 각 지사에서 본부까지의 최단 거리도 구한다.

2. 거리 계산:

   • 지사 간 메시지 전달 비용은 ((\text{본부까지 거리} + \text{본부에서 거리}))로 계산한다.

3. 동적 계획법 (DP):

   • DP 점화식:
     [
     \text{dp}[i][j] = \min_{k < j}(\text{dp}[i-1][k] + \text{cost}(k, j))
     ]
   • Divide and Conquer Optimization를 적용하여 효율적으로 계산.

코드

import java.io.*;
import java.util.*;

public class Main {
    static final int INF = Integer.MAX_VALUE;
    static int n, b, s, r;
    static int[] d, rd;
    static List<Pair>[] v, rv;
    static long[] sum;
    static long[][] dp;
    static int[][] p;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        d = new int[n + 1];
        rd = new int[n + 1];
        v = new ArrayList[n + 1];
        rv = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            v[i] = new ArrayList<>();
            rv[i] = new ArrayList<>();
        }

        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            v[start].add(new Pair(end, l));
            rv[end].add(new Pair(start, l));
        }

        dijkstra(b + 1, d, v);
        dijkstra(b + 1, rd, rv);

        List<Integer> value = new ArrayList<>();
        for (int i = 1; i <= b; i++) {
            value.add(d[i] + rd[i]);
        }
        Collections.sort(value);

        sum = new long[b + 1];
        for (int i = 1; i <= b; i++) {
            sum[i] = sum[i - 1] + value.get(i - 1);
        }

        dp = new long[s + 1][b + 1];
        p = new int[s + 1][b + 1];

        for (int i = 1; i <= b; i++) {
            dp[1][i] = sum[i] * (i - 1);
            p[1][i] = 1;
        }

        for (int i = 2; i <= s; i++) {
            dnqo(i, i, b, 0, b);
        }

        System.out.println(dp[s][b]);
    }

    static void dijkstra(int st, int[] dist, List<Pair>[] e) {
        Arrays.fill(dist, INF);
        dist[st] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.weight));
        pq.add(new Pair(st, 0));

        while (!pq.isEmpty()) {
            Pair curr = pq.poll();
            int td = curr.weight;
            int node = curr.node;

            if (td > dist[node]) continue;

            for (Pair next : e[node]) {
                int nd = td + next.weight;
                if (nd < dist[next.node]) {
                    dist[next.node] = nd;
                    pq.add(new Pair(next.node, nd));
                }
            }
        }
    }

    static long cost(int i, int j) {
        return (sum[j] - sum[i]) * (j - i - 1);
    }

    static void dnqo(int t, int l, int r, int pl, int pr) {
        if (l > r) return;
        int mid = (l + r) / 2;
        dp[t][mid] = Long.MAX_VALUE;

        for (int k = pl; k <= Math.min(mid - 1, pr); k++) {
            long tmp = dp[t - 1][k] + cost(k, mid);
            if (tmp < dp[t][mid]) {
                dp[t][mid] = tmp;
                p[t][mid] = k;
            }
        }

        dnqo(t, l, mid - 1, pl, p[t][mid]);
        dnqo(t, mid + 1, r, p[t][mid], pr);
    }

    static class Pair {
        int node, weight;

        Pair(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
}

코드 설명

1. 입력 처리:

   • 각 도로와 지사 정보를 입력받아 인접 리스트에 저장.

2. 다익스트라 알고리즘:

   • 본부에서 각 지사로, 각 지사에서 본부로의 최단 거리를 계산.

3. 거리 계산 및 정렬:

   • 각 지사의 (d[i] + rd[i])를 계산하여 정렬 후 누적합 계산.

4. DP 및 분할 정복 최적화:

   • DP를 계산하며 이전 그룹의 최적 위치만 탐색하여 시간 복잡도를 줄임.

5. 최종 출력:

   • 최소 이동 거리를 출력.

So...

이 문제는 그래프 탐색(다익스트라)과 DP 최적화(분할 정복)를 결합한 진형적인 문제였다.
분할 정복 최적화를 통해 큰 입력에서도 효율적으로 해결할 수 있었다.