[BOJ] 백준 2618 - 경찰차

문제 링크

www.acmicpc.net/problem/2618

2618번: 경찰차

 

풀이

저는 경로 추적이 생각보다 까다롭게 느껴졌습니다.

 

1번, 2번 경찰차가 각각 몇번 사건을 해결했는지를 상태로 둡시다.

$i$번 사건을 1번, 2번 경찰차가 해결하는 각 경우에 대해,

(경찰차의 마지막 위치 ~ $i$번 사건이 일어난 곳의 위치) 사이 거리를 더해주며 최솟값을 갱신하면 됩니다.

 

경로추적은 의외로 간단합니다.

발생한 사건을 순서대로 보며, $i$번 사건을 1번 경찰차가 해결했을 때의 거리 최솟값과 2번 경찰차가 해결했을 때의 거리 최솟값을 비교하여 더 작은 값을 가지는 경찰차를 출력해주면 됩니다.

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int d[1111][1111];
int n, w;
pii p[1111];

int getDist(int i, int j) {
    pii a = p[i];
    pii b = p[j];
    return abs(a.ft - b.ft) + abs(a.sd - b.sd);
}

int ans[1111];

int go(int now, int l, int r) {
    if (now == w) return 0;

    int &ret = d[l][r];
    if (ret != -1) return ret;
    int v1 = go(now + 1, now + 1, r) + getDist(l, now + 1);
    int v2 = go(now + 1, l, now + 1) + getDist(r, now + 1);
    ret = min(v1, v2);

    return ret;
}

void printPath(int now, int l, int r) {
    if (now == w) return;
    int v1 = go(now + 1, now + 1, r) + getDist(l, now + 1);
    int v2 = go(now + 1, l, now + 1) + getDist(r, now + 1);
    if (v1 < v2) {
        cout << 1 << '\n';
        printPath(now + 1, now + 1, r);
    } else {
        cout << 2 << '\n';
        printPath(now + 1, l, now + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> w;
    for (int i = 1; i < w + 1; i++) {
        cin >> p[i].ft >> p[i].sd;
    }
    p[0] = {1, 1};
    p[w + 1] = {n, n};
    memset(d, -1, sizeof(d));
    cout << go(0, 0, w + 1) << '\n';
    printPath(0, 0, w + 1);
}