[DP] BOJ 2618 경찰차

문제 링크 : www.acmicpc.net/problem/2618

2618번: 경찰차

문제의 부분 상황을 보자.

1, 2번 경찰차가 몇 개의 사건을 해결한 상황이다.

이제 새로운 사건이 발생했을 때, 가능한 경우는 1번 경찰차가 해결하거나, 2번 경찰차가 해결하는 두 가지가 존재한다. (부분문제)

이 때, 항상 가까운 경찰차가 문제를 해결하는 것은 최적해를 보장하지 못한다. 다음 사건의 위치를 미리 알고 있는게 아니기 때문이다.

따라서 이 문제는 다이나믹 프로그래밍으로 접근한다.

 

이제 부분문제를 해결하기 위해, 각 경찰차가 사건을 해결하는 두 경우에 대해 이동 거리를 계산해야 할 것이다.

하지만 각 경찰차의 위치를 알고 있어야만 하므로, 이 위치를 나타낼 적절한 방법을 생각해야 한다.

이 풀이에서는 DP배열을 다음과 같이 두었다.

"dp[i][j] = 1번 경찰차가 i번, 2번 경찰차가 j번 사건을 마지막으로 해결했을 경우 총 이동거리의 최솟값"

이를 통해 부분 문제에서 각 경찰차의 위치를 특정할 수 있다. (경찰차는 사건을 해결한 후 그 위치에서 대기하므로)

dp[0][0]에서 시작해, 두 인덱스 중 어느 하나가 마지막 사건 번호가 되었을 때의 모든 거리 최솟값들을 비교해 최종 답을 낸다.

 

다만 이 문제의 경우 오히려 경로 출력에서 애를 먹었는데, 이미 계산된 DP값들을 통해 DP배열을 채울 때와 같은 방식으로 구성하면 된다. (코드 참조)

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
#define INF 999999999
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n, w;
int dp[1001][1001];
vector<p> cases;
 
int get_dp(int pol1, int pol2) {
    if (dp[pol1][pol2] != INF) return dp[pol1][pol2];        //Memoization
    if (pol1 == w || pol2 == w) return 0;
 
    //이번에 해결해야 하는 사건의 번호
    int casenum = max(pol1, pol2) + 1;
    p cur_case = cases[casenum];
 
    //pol1 : 1번 경찰차가 마지막으로 해결한 사건 번호, pol2도 동일
    //마지막으로 해결한 사건 번호를 통해 경찰차들의 마지막 위치를 알 수 있다.
    p pos_1 = (pol1 == 0) ? make_pair(1, 1) : cases[pol1];
    p pos_2 = (pol2 == 0) ? make_pair(n, n) : cases[pol2];
 
    //현재 사건을 1번 경찰차가 해결
    int dist_1 = abs(cur_case.first - pos_1.first) + abs(cur_case.second - pos_1.second);
    int ret_1 = get_dp(casenum, pol2) + dist_1;
 
    //현재 사건을 2번 경찰차가 해결
    int dist_2 = abs(cur_case.first - pos_2.first) + abs(cur_case.second - pos_2.second);
    int ret_2 = get_dp(pol1, casenum) + dist_2;
 
    if (ret_1 < ret_2) dp[pol1][pol2] = ret_1;
    else dp[pol1][pol2] = ret_2;
 
    return dp[pol1][pol2];
}
 
void init() {
    int a, b;
    cin >> n >> w;
 
    for (int i = 0; i <= w; i++)
        for (int j = 0; j <= w; j++)
            dp[i][j] = INF;
    
    cases.push_back({ 0, 0 });
    for (int i = 0; i < w; i++) {
        cin >> a >> b;
        cases.push_back({ a, b });
    }
}
 
void print_history(int pol1, int pol2) {
    //pol1, pol2 상태에서 어느 쪽에 사건을 주는 것이 최적해를 내는지 판단
    if (pol1 == w || pol2 == w) return;
 
    //이번에 해결해야 하는 사건의 번호
    int casenum = max(pol1, pol2) + 1;
    p cur_case = cases[casenum];
 
    p pos_1 = (pol1 == 0) ? make_pair(1, 1) : cases[pol1];
    p pos_2 = (pol2 == 0) ? make_pair(n, n) : cases[pol2];
 
    //현재 사건을 1번 경찰차가 해결
    int dist_1 = abs(cur_case.first - pos_1.first) + abs(cur_case.second - pos_1.second);
    int ret_1 = get_dp(casenum, pol2) + dist_1;
 
    //현재 사건을 2번 경찰차가 해결
    int dist_2 = abs(cur_case.first - pos_2.first) + abs(cur_case.second - pos_2.second);
    int ret_2 = get_dp(pol1, casenum) + dist_2;
 
    //이 두 값을 통해 현재 상태에서 어느 쪽에 사건을 줄지 판단한다.
    if (ret_1 < ret_2) {
        printf("1\n");
        print_history(casenum, pol2);
    }
    else {
        printf("2\n");
        print_history(pol1, casenum);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    int answer = get_dp(0, 0);
    printf("%d\n", answer);
    print_history(0, 0);
 
    //system("PAUSE");
    return 0;
}