[Baekjoon,2618] 경찰차

경찰차의 위치와 처리해야 할 사건의 번호를 알면 둘 중 하나의 차량을 선택하여 더 작은 결과를 얻어내는 방향으로 선택해 나가며 결과를 얻으면 된다. 이를 초기에는 현재 경찰차 위치와 해결해야 하는 사건의 정보를 기준으로 부분 문제를 정의하여 해결하려 했다. 경찰차 위치와 현재 해결해야 하는 사건을 갖는 구조체를 정의하였고 이에 대해 map을 이용하여 메모이제이션을 시도했었다. 하지만 이는 현재 상태에 대한 정보가 너무 많아 처리 속도가 느리고 메모리도 엄청 차지하여 당연히 시간초과를 받았다. 그리고 경로를 찾는 과정도 차량의 위치 별로 나누지 않아 틀린 것을 볼 수 있다.

// 무식한 접근이었다. 
struct Pos;
struct Police;
int N,W;
vector<Pos> accident;
// car1 위치, car2 위치 
map<Police,int> cache;
int choices[MAX];

int dist(Pos a, Pos b);

int getMinMove(Police p)
{
    if(p.inCase==W)
        return 0;
    
    // 이미 존재하는 경우 
    if(cache.count(p)>0)
        return cache[p];
    int& ret=cache[p];
    
    // 두 차중 하나를 선택한다.
    Pos accPos=accident[p.inCase];
    
    int d=dist(accPos, p.car1);
    int cand1=d+getMinMove(Police(Pos(accPos), p.car2, p.inCase+1));
    
    d=dist(accPos, p.car2);
    int cand2=d+getMinMove(Police(p.car1, Pos(accPos), p.inCase+1));
    
    // 이런 식으로 경로를 찾으면 제대로 나오지 않는다. 
    choices[p.inCase]=(cand1<cand2) ? 1 : 2;
    return ret=min(cand1, cand2);
}

---

정보를 최소화 하자

그렇다면 정보를 어떻게 줄일 수 있을까? 방법은 경찰차의 위치를 해당 차량이 가장 최근에 해결한 사건의 인덱스로 저장하여 접근하는 것이다. 이렇게 하면 현재 어느 사건을 처리하는 지, 각 경찰차가 어느 위치에 있는 지 쉽게 알 수 있다. 현재 어느 사건을 처리하는 지는 두 차량이 최근에 처리한 사건의 인덱스 중 큰 값에 1을 더하면 구할 수 있다. 경찰차의 위치는 사건을 저장한 배열에 접근하면 얻을 수 있다. 이렇게 정보를 간략화 하면 메모이제이션에 쉽게 접근할 수 있다.

구현 시 아래처럼 초기 a,b 값을 -1로 설정하여 초기 위치에 대한 처리를 하는 것을 볼 수 있다.

// 현재 경찰차의 위치가 accident[a], accident[b]일 때 
// 움직여야 하는 거리의 최소 값을 반환 
// 초기 값은 a=-1, b=-1이다.
int getMinMove(int a, int b)
{
    // 사건을 모두 해결한 경우 
    if(a==W-1 || b==W-1)
        return 0;

    int& ret=cache[a+1][b+1];
    if(ret!=-1)
        return ret;
    
    // 해결해야 할 사건 정보  
    int accIdx=max(a,b)+1;
    pair<int,int> accPos=accident[accIdx];
    
    // a 경찰차로 처리 
    pair<int,int> apos=(a==-1) ? make_pair(1,1) : accident[a];
    int cand1=dist(apos,accPos)+getMinMove(accIdx,b);

    // b 경찰차로 처리 
    pair<int,int> bpos=(b==-1) ? make_pair(N,N) : accident[b];
    int cand2=dist(bpos,accPos)+getMinMove(a,accIdx);
    
    return ret=min(cand1, cand2);
}

---

경로 탐색

이제 경로를 추적하면 된다. 경로는 최소 움직임을 구하는 것처럼 접근하면 된다. 두 차량 중 더 적은 거리를 움직일 수 있는 차량을 선택해 출력하면 된다.

이에 대한 함수 구현은 아래와 같다. 여기서 이미 계산한 $cache$ 값을 $getMinMove$ 함수로 이용는 것을 볼 수 있다. 그리고 $getMinMove$ 함수와 거의 유사하다.

// 경로를 출력한다. 
void printPath(int a, int b)
{
    if(a==W-1 || b==W-1)
        return;
    
    int accIdx=max(a,b)+1;
    pair<int,int> accPos=accident[accIdx];
    // a 경찰차로 처리 
    pair<int,int> apos=(a==-1) ? make_pair(1,1) : accident[a];
    int cand1=dist(apos,accPos)+getMinMove(accIdx,b);

    // b 경찰차로 처리 
    pair<int,int> bpos=(b==-1) ? make_pair(N,N) : accident[b];
    int cand2=dist(bpos,accPos)+getMinMove(a,accIdx);
    
    // a 경찰차로 처리하는 결과가 더 작다면
    if(cand1<cand2)
    {
        cout<<1<<endl;
        printPath(accIdx,b);
    }
    else
    {
        cout<<2<<endl;
        printPath(a,accIdx);
    }
}

---

구현

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

const int MAX=1002;
const int INF=987654321;

int N,W;
vector<pair<int,int> > accident;
int cache[MAX][MAX];

int dist(pair<int,int> a, pair<int,int> b)
{
    return abs(a.first-b.first)+abs(a.second-b.second);
}

// 현재 경찰차의 위치가 accident[a], accident[b]일 때 
// 움직여야 하는 거리의 최소 값을 반환 
int getMinMove(int a, int b)
{
    // 사건을 모두 해결한 경우 
    if(a==W-1 || b==W-1)
        return 0;

    int& ret=cache[a+1][b+1];
    if(ret!=-1)
        return ret;
    
    // 해결해야 할 사건 정보  
    int accIdx=max(a,b)+1;
    pair<int,int> accPos=accident[accIdx];
    
    // a 경찰차로 처리 
    pair<int,int> apos=(a==-1) ? make_pair(1,1) : accident[a];
    int cand1=dist(apos,accPos)+getMinMove(accIdx,b);

    // b 경찰차로 처리 
    pair<int,int> bpos=(b==-1) ? make_pair(N,N) : accident[b];
    int cand2=dist(bpos,accPos)+getMinMove(a,accIdx);
    
    return ret=min(cand1, cand2);
}

// 경로를 출력한다. 
void printPath(int a, int b)
{
    if(a==W-1 || b==W-1)
        return;
    
    int accIdx=max(a,b)+1;
    pair<int,int> accPos=accident[accIdx];
    // a 경찰차로 처리 
    pair<int,int> apos=(a==-1) ? make_pair(1,1) : accident[a];
    int cand1=dist(apos,accPos)+getMinMove(accIdx,b);

    // b 경찰차로 처리 
    pair<int,int> bpos=(b==-1) ? make_pair(N,N) : accident[b];
    int cand2=dist(bpos,accPos)+getMinMove(a,accIdx);
    
    if(cand1<cand2)
    {
        cout<<1<<endl;
        printPath(accIdx,b);
    }
    else
    {
        cout<<2<<endl;
        printPath(a,accIdx);
    }
}

int main()
{
    cin>>N>>W;
    for(int i=0;i<W;++i)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        accident.push_back(make_pair(a,b));
    }
    memset(cache,-1,sizeof(cache));
    
    cout<<getMinMove(-1,-1)<<endl;
    printPath(-1,-1);
    return 0;
}