[백준 2618] 경찰차

 

  DP 문제이다. DP를 사용해야 한다는 것은 바로 알아챘지만, 점화식 떠올리는 게 쉽지 않았다. 계속 DP 테이블을 초기 상태부터 순서대로 채우려고 시도해서 그런 것 같다. 확실히 DP 문제에 약한 편이라, 같은 난이도여도 DP 문제는 더 어렵게 느껴진다.

 

 일단 브루트 포스 풀이를 생각해보면, 각 사건에 대해 경찰차1과 경찰차2를 배정하는 두 경우가 존재한다. 따라서 경우의 수가 2^W에 달하며, O(2^W)의 시간 복잡도를 가진다. 당연히 문제를 제 시간 내에 해결할 수 없다. 하지만 브루트 포스 로직을 관찰하면서 어떤 부분에서 비용을 줄일 수 있을지 생각해 볼 수 있다.

 

 특정 i 번째 사건에 경찰차를 배정하려고 할 때, 이전까지 경찰차를 배정하는 경우를 떠올려 보면, { 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 2 }, { 1, 1, 2, 1, 1 }, { 1, 1, 2, 1, 2 } ... 와 같은 수열들이 될 것이다. 그리고 i번 째 사건에는 경찰차1 혹은 경찰차2를 배정하게 될 것이고, 이때 이동 거리 합에 영향을 주는 요소는 경찰차들이 직전에 처리한 사건(위치)뿐이다. 따라서 최소 이동 거리 합을 구하기 위해서는 각 경찰차의 직전 처리 사건 정보만 필요하지, 그 이전에 처리한 사건들의 경우 필요 없다는 것을 알 수 있다. 대신에, 문제에서 각 사건마다 어떤 경찰차를 배정했는지도 출력하도록 요구하고 있으므로, DP에서 자주 사용되는 캐싱 및 역추적 기법이 필요할 것이라고 어느 정도 예상할 수 있다.

 

 브루트 포스 로직에서 어느정도 힌트를 얻었으므로, 이제 점화식을 떠올려야 한다. 나는 처음에 현재까지 이동한 거리를 기준으로 초기상태부터 최적 다음 상태를 찾아나가려 했는데, 그렇게 생각하니까 문제가 생겼다. 특정 시점에 경찰차를 중 하나를 배치할 때 최적해를 찾기 위해서 앞서 배치한 모든 경우를 모두 확인해봐야 했다. 그렇게 되면 DP 테이블을 채워나가는 매 루프마다 O(W^2)만큼의 시간 복잡도를 가지기 때문에, 시간 초과가 날 것이었다.

 

 이 시점에서, 한참을 헤매다가 얼마 전에 풀었던 트리 DP 문제가 떠올라서, DP 테이블을 채우는 방법을 바꾸기로 했다. 경찰차를 첫 사건마다 배치하는 경우, 미래에 대한 정보를 알 수 없기 때문에 필연적으로 이미 등장한 모든 케이스를 고려하게 된다. 하지만 반대로 생각해서, DP 테이블에는 남아있는 사건을 모두 처리하기 위한 최소 이동거리를 메모이제이션하고, 거꾸로 계산해 오면 상황은 달라진다.

 

 DP[a][b]에서, a를 경찰차1이 가장 마지막에 처리한 사건, b를 경찰차2가 가장 마지막에 처리한 사건이라고 했을 때, DP[a][b] 값은 다음 사건을 경찰차1로 처리하는 경우와 경찰차2로 처리하는 경우 단 두 가지 경우에만 영향을 받기 때문이다. 다음에 처리해야 하는 사건(next)은 a와 b중 큰 값에 1을 더해 바로 구할 수 있으므로, DP[a][b] = min(DP[next][b] + a사건 위치와 next사건 위치 사이 거리, DP[a][next] + b사건 위치와 next사건 위치 사이 거리)가 된다.

 이는 재귀와 DFS를 이용해 쉽게 구현할 수 있다. a든 b든, 마지막 사건을 처리하는 순간 남은 사건 처리를 위한 거리는 당연히 0이기 때문에, 종료 조건이 확실하기 때문이다. 

 

 근데 이렇게 처리하면 DP의 첫 부분, 그러니까 답이 기록될 부분인 초기상태를 나타내는 부분이 애매해진다. 경찰차1은 (1, 1)에 존재하고 경찰차2는 (N, N)에 존재하니까, 테이블의 한 값으로 처리하기 어렵다(DP[0][0]이라고 둔다고 했을 때, 0번째 사건과 다음 사건 사이의 거리 계산이 난처해진다). 물론, 함수로 한 번 감싸서, 경찰차1인지 경찰차2인지 확인해서 처리하는 방법도 있겠으나, 저 임의의 초기상태 사건 0을 위해 매번 그걸 확인하는 것은 썩 달갑지 않다.

 

 그래서 둘의 초기 상태를 분리해서 경찰차1의 초기 위치(사건)를 0번 사건으로 정의하고, 경찰차2의 초기 위치(사건)를 1번 사건으로 정의해 준다. 이는 입력받는 사건 배열을 2칸 더 길게 받고, 0번 사건과 1번 사건만 따로 초기화해주면 되기 때문에 훨씬 편리하고 효율적이다. 이후의 DP 계산 로직에도 전혀 문제가 없고.

 

 이제 위에서 구성한, DFS를 이용해 DP를 거꾸로 채워오는 함수를 solve(a, b)라고 하고 solve(0, 1)을 실행하면, 최종적으로 DP[0][1]에 찾고자 하는 최소 이동 거리 값을 알아낼 수 있다.

 문제가 여기서 끝이 아닌데, 브루트 포스 로직을 관찰할 때 예상했듯이 최소 비용뿐 아니라 실제 배치한 경찰차를 출력도 해주어야 하기 때문에 캐싱과 되추적도 필요하다.

 

 이 부분은 비교적 간단하게, 그냥 DP 테이블과 같은 크기의 캐싱용 테이블을 만들어두고, 각 시점에 어떤 경찰차를 배치했는지만 기록해두면 된다. 그러면 캐싱된 테이블의 [0][1] 값부터 하나씩 확인해 가며, 다음 사건에 배치된 경찰차 값을 알아내면서 되추적 할 수 있기 때문이다. DP 테이블을 채울 때 조금 더 비용이 들여서 필요한 경로 값만 저장할 순 있겠지만 메모리 제한을 가늠해 봤을 때 그럴 필요까진 없어 보여서 이 형태로 마무리했다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int n, w;
vector<pair<int, int> > incidentList;
vector<vector<int> > dp;
vector<vector<int> > prevList;

int getDist(pair<int, int>& p1, pair<int, int>& p2) {
    return abs(p1.first-p2.first) + abs(p1.second-p2.second);
}

int solve(int a, int b) {
    
    if(a==w+1 || b==w+1) dp[a][b] = 0;
    if(dp[a][b]!=-1) return dp[a][b];
    
    int nextIncident = max(a, b) + 1;
    int dist1 = solve(nextIncident, b) + getDist(incidentList[a], incidentList[nextIncident]); //경찰차1이 해결
    int dist2 = solve(a, nextIncident) + getDist(incidentList[b], incidentList[nextIncident]); //경찰차2가 해결

    if(dist1<dist2) {
        prevList[a][b] = 1;
        dp[a][b] = dist1;
    } else {
        prevList[a][b] = 2;
        dp[a][b] = dist2;
    }

    return dp[a][b];

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> w;
    
    int r, c;
    incidentList = vector<pair<int, int> >(w+2);
    for(int i=2; i<=w+1; i++) {
        cin >> r >> c;
        incidentList[i] = {r, c};
    }
    incidentList[0] = {1, 1};
    incidentList[1] = {n, n};

    dp = vector<vector<int> >(w+2, vector<int>(w+2, -1)); // [1번 경찰차][2번 경찰차]
    prevList = vector<vector<int> >(w+2, vector<int>(w+2, -1));

    cout << solve(0, 1) << "\n";

    int carInd1 = 0;
    int carInd2 = 1;
    
    while(carInd1<w+1 && carInd2<w+1) {
        cout << prevList[carInd1][carInd2] << "\n";
        if(prevList[carInd1][carInd2]==1) {
            carInd1 = max(carInd1, carInd2) + 1;
        } else {
            carInd2 = max(carInd1, carInd2) + 1;
        }
    }
}