백준) 2618 경찰차

2618. 경찰차

https://www.acmicpc.net/problem/2618

문제

어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다.

모든 도로에 는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방 향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.

이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 있다. 경찰 본부에서는 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려 주고, 연락 받은 경찰차는 그 위치로 가장 빠른 길을 통해 이동하여 사건을 처리한다. (하나의 사건은 한 대의 경찰차가 처리한다.) 그리고 사건을 처리 한 경찰차는 경찰 본부로부터 다음 연락이 올 때까지 처리한 사건이 발생한 위치에서 기다린다. 경찰 본부에서는 사건이 발생한 순서대로 두 대의 경찰차에 맡기려고 한다. 처리해야 될 사건들은 항 상 교차로에서 발생하며 경찰 본부에서는 이러한 사건들을 나누어 두 대의 경찰차에 맡기되, 두 대의 경찰차들이 이동하는 거리의 합을 최소화 하도록 사건을 맡기려고 한다.

예를 들어 앞의 그림처럼 N=6인 경우, 처리해야 하는 사건들이 3개 있고 그 사건들이 발생된 위치 를 순서대로 (3, 5), (5, 5), (2, 3)이라고 하자. (3, 5)의 사건을 경찰차2에 맡기고 (5, 5)의 사건도 경 찰차2에 맡기며, (2, 3)의 사건을 경찰차1에 맡기면 두 차가 이동한 거리의 합은 4 + 2 + 3 = 9가 되 고, 더 이상 줄일 수는 없다.

처리해야 할 사건들이 순서대로 주어질 때, 두 대의 경찰차가 이동하는 거리의 합을 최소화 하도록 사건들을 맡기는 프로그램을 작성하시오.

입력

첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나 타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 발생한 위치가 같을 수 있다.

출력

첫째 줄에 두 경찰차가 이동한 총 거리를 출력한다. 둘째 줄부터 시작하여 (i+1)번째 줄에 i(1≤i≤W)번째 사건이 맡겨진 경찰차 번호 1 또는 2를 출력한다.

예제 입력 

6
3
3 5
5 5
2 3

예제 출력 

9
2
2
1

1. 접근

그리디로는 풀 수 없다. 당장 가까운 경찰차를 보낸다고 하면, 남은 문제는 방금 푼 문제의 조건과 달라지기 때문이다.

그러면 당연히 다이나믹 프로그래밍으로 다 해봐야 한다!

2. 풀이

배열을 어떻게 잡아야 시간안에 풀 수 있을까? 즉, 공통된 계산부분을 잘 만들어내야한다.

모든 경우을 빡대가리처럼 다 계산해버리면 2 ^ 1000 만큼 계산해야 한다.

그럼 무엇이 공통된 사건일까? 중요한건 당연히 현재 경찰차 두대의 위치다.

사건 순서대로 경찰차가 출동한 순서를 예를들어 1->1->2->1->1 이라 해보자. 어쨌건 다섯번 출동하고 나서의 경찰차 두대의 위치는 2->1->2->1->1 와 같다. 경찰차 1은 다섯번째 사건위치에 있을 것이며, 경찰차 2는 세번째 사건위치에 있을 것이다.

그러면 우리는 dp배열을 다음과 같이 정의할 수 있다. dp[x][y] = 현재 경찰차 위치가 x, y 일 때 남은 최소이동거리.

문제는 지금까지 몇번 출동했는지를 모른다는 점이다. 하지만 경찰차 위치는 {1,1} 아니면 {n,n} 아니면 사건위치 이므로, 간략히 0~n 까지의 번호가 부여된 위치로 대체할 수 있다. 동시에 지금까지 얼마나 사건을 처리했는지도 알 수 있다.

따라서 dp[x][y] = 현재 경찰차가 가장 최근에 처리한 사건이 x, y 일 때 남은 최소이동거리. 라고 정의한다.

max(x,y) = k 라면 지금까지 k번째 사건까지 출동했다는 이야기가 된다. 그러면 이제 k+1 사건에 대해 두 대를 출동시켜보고 최소인 경우로 리턴해주면 되겠다.

문제에서 요구하는 답은 추가적으로 사건마다 어떤 경찰차가 출동했는지도 출력해야 한다. 어떻게 알 수 있을까?

dp배열을 갱신하면서 값을 알 수 있는 방법도 분명있다. (하지만 내가 빡대가리라 따로 구하기로 한다.)

dp배열을 모두 갱신하고 나면, 각 칸마다의 정보를 이용해서 어떤 경찰차가 출동했는지 알 수 있다.

만약 dp[1][2] = 10 이고, 확장되는 두 가지 dp[1][3] = 7, dp[3][2] = 5 라면, 당연히 1번 차를 출동시켜 3번 사건을 맡게 했다는 뜻이다.

모든 경우에 대해 이미 계산이 끝났으므로, 사건 수만큼 재귀를 돌고 어떤 차가 출동했는지 알 수 있다.

3. 코드

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
 
int n, w;
struct col {
    int x, y;
};
col fir[1001], sec[1001];
int dp[1001][1001];
 
int func(int c1, int c2) {
    if (c1 == w || c2 == w)
        return 0;
 
    int& ref = dp[c1][c2];
    if (ref != -1)
        return ref;
 
    int np = max(c1, c2) + 1;
    int n1 = abs(fir[c1].x - fir[np].x) + abs(fir[c1].y - fir[np].y);
    int n2 = func(np, c2) + n1;
 
    int m1 = abs(sec[c2].x - sec[np].x) + abs(sec[c2].y - sec[np].y);
    int m2 = func(c1, np) + m1;
 
    return ref = min(n2, m2);
}
 
vector<int> v;
void tracking(int c1, int c2) {
    if (c1 == w || c2 == w)
        return;
 
    int np = max(c1, c2) + 1;
    int n1 = abs(fir[c1].x - fir[np].x) + abs(fir[c1].y - fir[np].y);
    int n2 = dp[np][c2] + n1;
 
    int m1 = abs(sec[c2].x - sec[np].x) + abs(sec[c2].y - sec[np].y);
    int m2 = dp[c1][np] + m1;
 
    if (n2 > m2) {
        v.push_back(2);
        tracking(c1, np);
    }
    else {
        v.push_back(1);
        tracking(np, c2);
    }
}
 
int main() {
    scanf("%d %d", &n, &w);
 
    fir[0] = { 1,1 };
    sec[0] = { n,n };
    for (int i = 1; i <= w; ++i) {
        scanf("%d %d", &fir[i].x, &fir[i].y);
        sec[i] = { fir[i].x, fir[i].y };
    }
 
    memset(dp, -1, sizeof(dp));
    printf("%d\n", func(0, 0));
 
    tracking(0, 0);
    for (auto a : v)
        printf("%d\n", a);
 
    return 0;
}