BOJ 2618 경찰차 해설

작성일 | In

문제 링크

https://www.acmicpc.net/problem/2618

해설

알고리즘 분류

DP와 역추적을 이용하는 문제로, 두 경찰차의 위치와 그 비용을 저장하는 방식의 DP를 사용할 수 있습니다.

점화식 유도

역추적 문제라는 것이 훤하게 드러나기 때문에 2차원 배열로 DP를 구성하는 것이 가장 적절하다고 판단하였습니다.
두 경찰차가 사건으로 이동하는 경우의 수가 2의 거듭제곱 만큼 증가할 것이라 예상하고 완전이진 트리의 모습을 그릴 것이라 예상하였지만, 사실 도달하는 위치가 같은 좌표에서는 비용이 적은 곳을 선택하면 되기 때문에 파스칼의 삼각형(?)의 모양처럼 뻗어나가는 모습을 볼 수 있었습니다.
물론 파스칼의 삼각형과 아무런 연관이 없음으로, 그냥 2차원 배열에 데이터를 집어넣는다는 생각으로 공식을 유도했습니다.
설명한 바를 공식으로 유도하면 아래와 같습니다.

$f(x, y) = max(f(x - 1, y) + \alpha, f(x, y - 1) + \beta)$
참고로 $\alpha$와 $\beta$는 각각의 경찰차와 사건 장소 사이의 거리입니다.

뭔가 그럴싸해 보이는 점화식이지만, 아직 수정해야 할 부분이 있습니다.
바로 사건이 두 인덱스 $x$와 $y$에서 겹친다는 것입니다.
예를 들어 1번 사건이 $x$에서 한번 진행되고, 나중에 $y - 1$에서 한번 진행하는 등, 중복을 배제해야 합니다.
그렇기 때문에 실제로는 $x$ 값이 갱신할 때, $x + 1$로 갱신하는 것이 아닌, $max(x, y) + 1$로 갱신해야 하며, $y$도 마찬가지입니다.

보통 역추적 문제에서는 $x - 1$이랑 $y - 1$을 비교하는 것이 가장 일반적이지만, $x$ 값과 $y$ 값이 어떻게 갱신될지 모르기 때문에 부모 정보를 따로 저장해야 합니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

typedef struct police {
    ll x1, x2, y1, y2;
    ll ans = LLONG_MAX;
    ll bef;
    pair<ll, ll> par;
}police;

int main(void) {
    ios::sync_with_stdio(0);
    ll n;
    cin >> n;
    ll w;
    cin >> w;
    vector<ll> a(w + 1);
    vector<ll> b(w + 1);
    for (ll i = 1; i <= w; i++) {
        cin >> a[i] >> b[i];
    }
    vector<vector<police>> cache(w + 1, vector<police>(w + 1));
    police tmp;
    tmp.x1 = 1; tmp.y1 = 1; tmp.x2 = n; tmp.y2 = n; tmp.ans = 0;
    cache[0][0] = tmp;
    ll _max = LLONG_MAX;
    ll x, y;
    for (ll i = 0; i <= w; i++) {
        for (ll j = 0; j <= w; j++) {
            ll k = max(i, j) + 1;
            if (k > w || cache[i][j].ans == LLONG_MAX) continue;
            ll cost = abs(a[k] - cache[i][j].x1);
            cost += abs(b[k] - cache[i][j].y1);
            cost += cache[i][j].ans;
            if (cache[k][j].ans > cost) {
                cache[k][j].bef = 1;
                cache[k][j].ans = cost;
                cache[k][j].x1 = a[k];
                cache[k][j].y1 = b[k];
                cache[k][j].x2 = cache[i][j].x2;
                cache[k][j].y2 = cache[i][j].y2;
                cache[k][j].par = {i, j};
            }
            if (k == w && _max > cache[k][j].ans) {
                _max = cache[k][j].ans;
                x = k;
                y = j;
            }
            cost = abs(a[k] - cache[i][j].x2);
            cost += abs(b[k] - cache[i][j].y2);
            cost += cache[i][j].ans;
            if (cache[i][k].ans > cost) {
                cache[i][k].bef = 2;
                cache[i][k].ans = cost;
                cache[i][k].x1 = cache[i][j].x1;
                cache[i][k].y1 = cache[i][j].y1;
                cache[i][k].x2 = a[k];
                cache[i][k].y2 = b[k];
                cache[i][k].par = {i, j};
            }
            if (k == w && _max > cache[i][k].ans) {
                _max = cache[i][k].ans;
                x = i;
                y = k;
            }
        }
    }
    cout << _max << "\n";
    vector<ll> res(w);
    for (ll i = w - 1; i >= 0; i--) {
        res[i] = cache[x][y].bef;
        ll alp = x;
        ll beta = y;
        x = cache[alp][beta].par.first;
        y = cache[alp][beta].par.second;
    }
    for (ll i = 0; i < w; i++) {
        cout << res[i] << "\n";
    }
}