BOJ 2618번: 경찰차

문제 링크

DP만 쓰면 되는 문제인데, 난이도가 플래티넘 V로 나에게는 어려운 편인 문제였다! 당연히 안 되겠지만, 완전 탐색으로 푼다면 결국 각각의 사건에 대해 1번 경찰차가 출동하면 되는지, 2번 경찰차가 출동하면 되는지를 판단하면 되니까 최대 $2^{1000}$가지의 경우가 존재할 것이다.

여기서 중복된 계산이 여러 번 나오면 DP를 적용하면 되는데, 처음에는 최적 부분 구조(optimal substructure)가 성립하는지에 대한 의심을 해 보았다!

$w$개의 사건을 해결하는 최적의 선택을 $A$라고 했을 때, 여기서 새로운 사건이 추가되었을 때 $(w+1)$개의 사건을 해결하는 최적의 경로는 $A$를 포함하는가?

이것이 사실이라면 새로운 사건이 추가될 때마다, 1번 경찰차 혹은 2번 경찰차가 출동하는 두 가지 경우만 고려하면 되기 때문에 매우 쉽게 문제를 풀 수 있겠지만 그렇지 않다.

위 그림에서, 해결해야 할 사건이 1번과 2번일 때는 1번 경찰차가 모두 사건을 처리하거나 2번 경찰차가 모두 처리하거나, 2번 경찰차가 사건 1을 처리하고 1번 경찰차가 사건 2를 처리하는 방법 모두 최소의 비용이 들지만, 여기에 사건 3이 추가된다면, 2번 경찰차가 사건 2를 해결하게 되었을 때는 최소의 비용으로 사건을 해결할 수 없게 된다.

결국 DP를 적용한다고 하더라도, 사건을 하나씩 추가해 가는 방식으로는 최적의 해를 얻을 수 없다!

일반적으로 DP를 이용해 문제를 해결할 때, bottom-up 방식과 top-down 방식이 있는데 여기서는 위와 같은 이유로 bottom-up 방식을 사용할 수 없어 top-down 방식으로 풀어야 할 것이다.

먼저 메모이제이션(memoization)을 적용할 대상을 찾아야 하는데, top-down 방식을 사용한다는 점과 위의 굵은 글씨에서 힌트를 찾는다면 다음과 같이 정의할 수 있을 것이다.

$dp(i, j)$: 1번 경찰차가 마지막으로 해결한 사건이 $i$, 2번 경찰차가 마지막으로 해결한 사건이 $j$일 때 앞으로 남은 이동 거리의 최솟값

이때 구하고자 하는 답은 $dp(0, 0)$이 될 것이다.

초깃값은 다음과 같이 설정할 수 있다.

For $0 \le i \le w$, $dp(w, i) = 0$, $dp(i, w) = 0$

다음 사건을 해결하는 경우는 1번 경찰차와 2번 경찰차가 해결하는 두 가지 경우가 있으므로, 점화식은 다음과 같다.

$k = max(i,j) + 1$
$dp(i, j) = min[dp(i, k) + dist(j, k), dp(k, j) + dist(i, k)]$

마지막으로, 최소 비용뿐만 아니라 최적의 선택을 하는 경찰차의 번호까지 알고자 한다면 위의 점화식을 만족시키는 방향이 1번 경찰차를 선택할 때인지, 2번 경찰차를 선택할 때인지를 찾아 저장하거나 출력하면 된다.

// BOJ 2618. 경찰차

#include <iostream>
#include <cmath>
#include <vector>

const int INF {999999999};

int n, w;
// cases[i] is the place of case i.
// cases[0] is a special state, where car 1 and car 2 are on starting point (0, 0), (n - 1, n - 1).
std::vector<std::pair<int, int>> cases {std::make_pair(-1, -1)};

// dp[i][j] is the remaining distance,
// where car 1 is at the place of case i and car 2 is at the place of case j.
int dp[1001][1001];

// Returns the distance between two places where case a and b occured.
int dist(std::pair<int, int> a, std::pair<int, int> b) {
    return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}

int solve(int i, int j) {
    // Memoization
    if (dp[i][j] != INF) return dp[i][j];
    // Let the index of next case to visit be k.
    int k = std::max(i, j) + 1;
    // Get positions of car 1 and car 2.
    auto car1 = (i == 0) ? std::make_pair(0, 0) : cases[i];
    auto car2 = (j == 0) ? std::make_pair(n - 1, n - 1) : cases[j];
    // Either car 1 or car 2 can visit the case k.
    int car1_dist = dist(car1, cases[k]) + solve(k, j);
    int car2_dist = dist(cases[k], car2) + solve(i, k);
    if (car1_dist < car2_dist) dp[i][j] = car1_dist; 
    else dp[i][j] = car2_dist;
    return dp[i][j];
}

void print_path(int i, int j) {
    // End of printing.
    if (i == w || j == w) return;
    // Find choices that makes the minimum distance in similar way of function 'solve'.
    // However, there's no recursion of 'solve' since we already stored all values in array 'dp'.
    int k = std::max(i, j) + 1;
    auto car1 = (i == 0) ? std::make_pair(0, 0) : cases[i];
    auto car2 = (j == 0) ? std::make_pair(n - 1, n - 1) : cases[j];
    int car1_dist = dist(car1, cases[k]) + solve(k, j);
    int car2_dist = dist(cases[k], car2) + solve(i, k);
    if (car1_dist < car2_dist) {
        std::cout << 1 << std::endl;
        print_path(k, j);
    } else {
        std::cout << 2 << std::endl;
        print_path(i, k);
    }
}

int main() {
    // Input
    std::cin >> n >> w;
    for (int i=0; i<w; i++) {
        int y, x;
        std::cin >> y >> x;
        cases.push_back(std::make_pair(y - 1, x - 1));
    }
    // Initialization for dynamic programming.
    for (int i=0; i<=w; i++)
        for (int j=0; j<w; j++) dp[i][j] = INF;
    for (int i=0; i<=w; i++) {
        dp[w][i] = 0;
        dp[i][w] = 0;
    }
    // Output
    std::cout << solve(0, 0) << std::endl;
    print_path(0, 0);
    return 0;
}