백준 BOJ 2618번 : 경찰차 (다이나믹 프로그래밍, Platinum V)

백준 BOJ 2618번 : 경찰차

 

N×N 크기의 도로가 있고 1번 경찰차는 (1, 1), 2번 경찰차는 (N, N)의 위치에 있다고 합니다.

W개의 사건이 일어나는 좌표가 주어질 때, 두 개 중 하나의 경찰차를 움직여 해당 좌표로 이동을 시켜야하며 이 때 반드시 사건이 발생한 순서대로 이동이 발생해야합니다.

이동한 경찰차는 해당 좌표에 머물러 있다가 다음 이동에 그 자리로부터 이동한다고 할 때, W개의 사건을 모두 해결하는데 필요한 두 경찰차 이동 거리의 합의 최솟값과 그 때 이동한 경찰차의 번호를 순서대로 구하는 문제입니다.

 

dp[i][j]를 1번 차가 마지막으로 i번째 좌표에 이동했고, 2번 차가 마지막으로 j번째 좌표에 이동했다고 했을 때 "앞으로 가야할 최소 거리"라고 정의합니다.

 

dp[i][j]를 구하기 위해서 필요한 변수를 생각해봅시다.

먼저 가장 최근의 사건을 경찰차 1 또는 2 둘 중 하나가 처리했을 것이고 번호가 더 높은 사건이 더 후순위에 발생하는 사건이므로, next = max(i, j)가 다음 사건의 번호가 될 것입니다. (간단하게 next라고 합시다.)

그리고 이번 사건에 대해서 경찰차 1번이 사건 위치로 이동하는데 필요한 이동 거리를 dist1, 경찰차 2번이 사건 위치로 이동하는데 필요한 이동 거리를 dist2라고 합시다.

그러면 이번 사건에 대한 앞으로 남은 최소 이동거리는, 1번 경찰차가 이동하고 나서 다음 사건부터 이동할 거리(+ 이번 이동 거리)와 2번 경찰차가 이동하고 나서 다음 사건부터 이동할 거리(+ 이번 이동 거리) 중 더 작은 값을 취해주면 되므로, dp에 대한 점화식을 다음과 같이 나타낼 수 있습니다.

 

∴ dp[i][j] = min(dp[next][j] + dist1, dp[i][next] + dist2)

 

위의 점화식을 활용하여 dp[0][0]을 끝 번호부터 재귀적으로 구해와 답을 출력해주면 됩니다.

 

 

이제 추가로 사건 번호에 따라 이동할 경찰차의 번호를 찾아 출력해보는 함수를 구현해봅시다.

이 또한 완전히 동일한 방식으로 가능한데, dp 값은 앞서 이미 다 구했으므로 이제 dp[next][j] + dist1과 dp[i][next] + dist2를 비교해서 거리가 더 작은 쪽의 경찰차 번호를 출력해주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MAX 1001
using namespace std;

struct Point { int x, y; };
Point point[MAX];

int N, W;
int dp[MAX][MAX]; // dp[i][j] : minimum distance to go since "car 1 last visited point i" and "car 2 last visited point j"

int dist(Point a, Point b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int calc_dp(int i, int j) {
    if(i == W || j == W) return 0;
    if(dp[i][j] != -1) return dp[i][j];

    int dist1, dist2, next = max(i, j) + 1;

    if(i == 0) dist1 = dist({1, 1}, point[next]);
    else dist1 = dist(point[i], point[next]);

    if(j == 0) dist2 = dist({N, N}, point[next]);
    else dist2 = dist(point[j], point[next]);

    return dp[i][j] = min(calc_dp(next, j) + dist1, calc_dp(i, next) + dist2);
}

void car_num(int i, int j) {
    if(i == W || j == W) return;

    int dist1, dist2, next = max(i, j) + 1;

    if(i == 0) dist1 = dist({1, 1}, point[next]);
    else dist1 = dist(point[i], point[next]);

    if(j == 0) dist2 = dist({N, N}, point[next]);
    else dist2 = dist(point[j], point[next]);

    if(dp[next][j] + dist1 < dp[i][next] + dist2) {
        cout << "1\n";
        car_num(next, j);
    }
    else {
        cout << "2\n";
        car_num(i, next);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> W;

    for(int i=1; i<=W; i++)
        cin >> point[i].x >> point[i].y;

    memset(dp, -1, sizeof(dp));

    cout << calc_dp(0, 0) << "\n";

    car_num(0, 0);
}