백준 2618 - 경찰차 (C++)

문제

• 문제 링크

  
   BOJ 2618 - 경찰차 
  

• 문제 요약

$2$차원 맵에서 $w$개의 사건이 발생한다.
두 대의 경찰차가 사건을 순차적으로 해결할 때, 두 대의 경찰차가 이동하는 거리의 합을 최소로 하는 경로를 찾아보자.

• 제한

TL : $1$ sec, ML : $128$ MB




$5 ≤ N ≤ 1,000$

$1 ≤ W ≤ 1,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

플래티넘 $dp$계의 수문장같은 바이블 문제이다.
결국 매 시점마다 변하는 상태는 경찰차들의 위치 뿐이다. 이에 따라 다음과 같이 정의를 내려보자.

$dp[p][q]$ : 각 경찰차의 마지막으로 해결한 사건 번호가 각각 $p, q$일 때 이동하는 거리 합의 최솟값.

이런 문제는 사실 위처럼 점화식 정의를 내리기까지가 문제이지 막상 정의를 내렸다면 점화식은 세상 간단하다.
거리 계산( $d_i$ )은 유클리드 거리가 아닌 택시 거리로써 계산된다.
구체적으로 다음 사건 번호를 $k$라 할 때

$dp[p][q] = min( dp[k][q] + d_1, dp[p][k] + d_2 )$

최초 첫번째 경찰차는 $(1, 1)$, 두번째 경찰차는 $(N, N)$ 에서 시작 한다는 것을 주의하자.

---

역추적이 은근 복병이라고 하는데, 나는 그냥 가장 직관적이게 처리했다.
최적해를 찾았다는 가정 하에 그 경로를 출력하기 위해선 $3$개의 값(다음 이동의 $p, q$ 상태 및 어느 경찰차가 이동 했는지)이 필요 하다고 생각했다.

즉, 위에서

• $dp[k][q] + d_1$ 가 최적해 였다면 $pt[p][q] = (k, q, 1)$ 가 되고
• $dp[p][k] + d_2$ 가 최적해 였다면 $pt[p][q] = (p, k, 2)$ 가 된다.

따라서 호출이 $f(0, 0)$으로 시작 됐음에 따라 역추적 출력도 $(0, 0)$을 시작으로 쭉죽 뽑아주면 된다.

전체 코드

#include<bits/stdc++.h>
#define N 1001
using namespace std;
 
struct { int p, q, w; } pt[N][N];
int n, w, a[N]{ 1 }, b[N]{ 1 }, dp[N][N];
 
int f(int p, int q)
{
    int& t(dp[p][q]), k(max(p, q));
    if (k++ == w) return 0;
    if (!~t)
    {
        t = 2e9;
        int x(f(k, q) + abs(a[k] - a[p]) + abs(b[k] - b[p]));
        int y(f(p, k) + (q ? abs(a[k] - a[q]) + abs(b[k] - b[q]) : n - a[k] + n - b[k]));
        if (t > x) t = x, pt[p][q] = { k, q, 1 };
        if (t > y) t = y, pt[p][q] = { p, k, 2 };
    }
    return t;
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n >> w;
    for (int i(1); i <= w; i++) cin >> a[i] >> b[i];
    cout << f(0, 0) << '\n';
    for (int x{}, y{}; pt[x][y].w; x = pt[x][y].p, y = pt[n][y].q)
        cout << pt[x][y].w << '\n', n = x;
}

comment

끝