경찰차

 

간단하게 경찰차 두대에 사건을 맡겨서 이동거리 합이 최소가 되게 하면 된다.

N,W는 1000이하이다.

 

dp로 풀면 되는데, dp[i][j]를 경찰차 1이 마지막으로 해결한 사건 번호가 i, 경찰차 2가 마지막으로 해결한 사건 번호가 j일 때 이동거리의 합의 최소로 정의한다.

이렇게 하고 dp[i][j]에서 i,j중 큰 사건 번호가 마지막으로 해결한 것이기 때문에 max(i,j)+1을 경찰차1한테 배정했을 때와

경찰차2한테 배정했을 때의 이동거리를 dp값과 비교해서 더 작은 것으로 채워나가는 식으로 하면 된다.

void solve()
{
    dp[1][2]=0;
    police.push({1,2,0});
    while(!police.empty())
    {
        Data t = police.top();
        police.pop();
        int next = max(t.one,t.two)+1;
        if(next>W+2)
        {
            ans = dp[t.one][t.two];
            last_one = t.one;
            last_two = t.two;
            break;
        }
        int first = t.dis+dist(t.one,next);
        if(dp[next][t.two]>first || dp[next][t.two]==-1)
        {
            dp[next][t.two] = first;
            police.push({next,t.two,first});
        }
        int second = t.dis+dist(t.two,next);
        if(dp[t.one][next]>second || dp[t.one][next]==-1)
        {
            dp[t.one][next] = second;
            police.push({t.one,next,second});
        }
    }
}

 

처음으로 next가 W+2를 넘어갈 때 바로 break를 해도 되는 이유는 어차피 우선 순위 큐로 저장을 했기 때문에 이동거리가 제일

작은게 먼저 나오기 때문이다.

 

근데 여기서 문제는 어떤 사건에 어떤 경찰차가 갔는지도 출력해야 한다.

예전에 풀었던 임계경로 문제에서도 비슷한 경우가 있었다.

(참조)  https://bluesunset-hack.tistory.com/224

임계경로

 

이런 경우에는 역으로 돌면서 어떻게 최솟값이 나오게 되었는지 경로를 찾으면 된다.

dp[i][j]가 모든 사건을 해결했을 때 나오는 dp값들 중 최소라고 하고, j가 N이라고 가정하면,

i+1~N번은 2번 경찰차가 해결했을 것이다.

그리고 i번은 1번 경찰차가 해결했을 것이다.

이제 여기서부터 중요한데 dp[i][i+1]이 어디서 왔는지를 봐야 한다.

dp[i][1]부터 dp[i][i-1] 까지 돌면서 dp[i][i+1] = dp[i][x]+(x와 i+1 사이의 거리) 를 만족하는 x를 찾아야 한다.

그렇게 해서 x를 찾았으면, 또 마찬가지로 dp[x+1][x] = dp[y][x]+(y와 x+1 사이의 거리) 를 만족하는 y를 찾아야 한다.

이 작업을 반복하면 된다.

void backtrack()
{
    int x = last_one;
    int y = last_two;
    while(1)
    {
        if(x<y)
        {
            for(int i=x+1;i<=y;i++)
            {
                nums[i]=2;
            }
            nums[x]=1;
            if(x==1 || y==2) break;
            for(int i=2;i<=x-1;i++)
            {
                if(dp[x][i]!=-1 && dp[x][i]+dist(i,x+1)==dp[x][x+1])
                {
                    y = i;
                    break;
                }
            }
        }
        if(x>y)
        {
            for(int i=y+1;i<=x;i++)
            {
                nums[i]=1;
            }
            nums[y]=2;
            if(x==1 || y==2) break;
            for(int i=1;i<=y-1;i++)
            {
                if(dp[i][y]!=-1 && dp[i][y]+dist(i,y+1)==dp[y+1][y])
                {
                    x = i;
                    break;
                }
            }
        }
    }
}

이렇게 구현할 수 있다.

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int N,W;
pair<int,int> event[1005];
int dp[1005][1005];
int ans;
int nums[1005];
int last_one,last_two;
struct Data
{
    int one,two,dis;
    bool operator<(const Data r)const{
        return dis>r.dis;
    }
};
priority_queue<Data>police;
//distance between event[a] and event[b]
int dist(int a, int b)
{
    int horr = abs(event[a].first-event[b].first);
    int ver = abs(event[a].second-event[b].second);
    return horr + ver;
}
void solve()
{
    dp[1][2]=0;
    police.push({1,2,0});
    while(!police.empty())
    {
        Data t = police.top();
        police.pop();
        int next = max(t.one,t.two)+1;
        if(next>W+2)
        {
            ans = dp[t.one][t.two];
            last_one = t.one;
            last_two = t.two;
            break;
        }
        int first = t.dis+dist(t.one,next);
        if(dp[next][t.two]>first || dp[next][t.two]==-1)
        {
            dp[next][t.two] = first;
            police.push({next,t.two,first});
        }
        int second = t.dis+dist(t.two,next);
        if(dp[t.one][next]>second || dp[t.one][next]==-1)
        {
            dp[t.one][next] = second;
            police.push({t.one,next,second});
        }
    }
}
void backtrack()
{
    int x = last_one;
    int y = last_two;
    while(1)
    {
        if(x<y)
        {
            for(int i=x+1;i<=y;i++)
            {
                nums[i]=2;
            }
            nums[x]=1;
            if(x==1 || y==2) break;
            for(int i=2;i<=x-1;i++)
            {
                if(dp[x][i]!=-1 && dp[x][i]+dist(i,x+1)==dp[x][x+1])
                {
                    y = i;
                    break;
                }
            }
        }
        if(x>y)
        {
            for(int i=y+1;i<=x;i++)
            {
                nums[i]=1;
            }
            nums[y]=2;
            if(x==1 || y==2) break;
            for(int i=1;i<=y-1;i++)
            {
                if(dp[i][y]!=-1 && dp[i][y]+dist(i,y+1)==dp[y+1][y])
                {
                    x = i;
                    break;
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&N);
    scanf("%d",&W);
    for(int i=3;i<=W+2;i++)
    {
        scanf("%d %d",&event[i].first,&event[i].second);
    }
    event[1]=make_pair(1,1);
    event[2]=make_pair(N,N);
    for(int i=1;i<=W+2;i++)
    {
        for(int j=1;j<=W+2;j++)
        {
            dp[i][j]=-1;
        }
    }
    ans = -1;
    solve();
    backtrack();
    printf("%d\n",ans);
    for(int i=3;i<=W+2;i++) printf("%d\n",nums[i]);
}

전체 코드이다.