BOJ 2618 - 경찰차 링크
(2023.08.29 기준 P4)

문제

N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있는 도시에서, 경찰차1은 (1, 1)에, 경찰차2는 (N, N)에 있다.
사건 W개가 발생한 순서대로 각 사건의 위치가 주어지며, 경찰차1과 경찰차2 중 한 대가 맡아서 사건이 발생한 위치에 가야 한다. 이 때, 두 대의 경찰차가 이동하는 거리의 합이 최소화될 때의 거리와 각 사건을 맡는 경찰차 번호 출력

알고리즘

DP

풀이

i(1 ≤ i ≤ W)번 사건이 발생할 때, 경찰차가 움직이는 경우의 수는 크게 4가지로 분류할 수 있다.

1) 1번 경찰차는 0 ~ i-2번 위치에서 i번 위치로, 2번 경찰차는 i-1번 위치에서 대기
2) 1번 경찰차는 i-1번 위치에서 대기, 2번 경찰차는 0 ~ i-2번 위치에서 i번 위치로
3) 1번 경찰차는 i-1번 위치에서 i번 위치로, 2번 경찰차는 0 ~ i-2번 위치에서 대기
4) 1번 경찰차는 0 ~ i-2번 위치에서 대기, 2번 경찰차는 i-1번 위치에서 i번 위치로

위 네 경우에 맞게 dp 테이블을 채워나가면 된다.
물론, 1번 사건은 두 경찰차 모두 0번 위치(처음 위치)에 있어서 위 네 경우에 해당하지 않는다. 그러므로 dp[1][0], dp[0][1]은 각 경찰차와 1번 사건의 거리로 직접 채워주자.

그리고 역추적 부분에서도 똑같이 위 네 경우를 살펴봐서 거리와 dp 값이 일치하는 쪽으로 역추적을 진행하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

const int inf = INT_MAX;

int dist(pii a, pii b){
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, W; cin >> N >> W;
    pii P[W + 1]; for (int i = 1; i <= W; i++) cin >> P[i].x >> P[i].y;

    int dp[W + 1][W + 1]; fill(&dp[0][0], &dp[W][W + 1], inf);
    dp[0][0] = 0; // 두 경찰차의 처음 위치에서의 총 이동 거리는 0
    dp[1][0] = dist({1, 1}, P[1]); // 경찰차 1번이 1번 사건으로 갔을 때의 이동 거리
    dp[0][1] = dist({N, N}, P[1]); // 경찰차 2번이 1번 사건으로 갔을 때의 이동 거리

    for (int i = 2; i <= W; i++) // 2번 사건부터 dp 테이블을 채워 나간다.
        for (int j = 0; j <= i - 2; j++){
            // 1번 경찰차는 0 ~ i-2번 위치에서 i번 위치로, 2번 경찰차는 i-1번 위치에서 대기
            dp[i][i - 1] = min(dp[i][i - 1], dp[j][i - 1] + (j ? dist(P[j], P[i]) : dist({1, 1}, P[i])));
            // 1번 경찰차는 i-1번 위치에서 대기, 2번 경찰차는 0 ~ i-2번 위치에서 i번 위치로
            dp[i - 1][i] = min(dp[i - 1][i], dp[i - 1][j] + (j ? dist(P[j], P[i]) : dist({N, N}, P[i])));
            // 1번 경찰차는 i-1번 위치에서 i번 위치로, 2번 경찰차는 0 ~ i-2번 위치에서 대기
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + dist(P[i - 1], P[i]));
            // 1번 경찰차는 0 ~ i-2번 위치에서 대기, 2번 경찰차는 i-1번 위치에서 i번 위치로
            dp[j][i] = min(dp[j][i], dp[j][i - 1] + dist(P[i - 1], P[i]));
        }

    // 이동 거리가 제일 짧을 때의 두 경찰차의 위치까지 저장
    int min_dist = inf, a, b;
    for (int i = 0; i < W; i++){
        if (dp[W][i] < min_dist){
            min_dist = dp[W][i];
            a = W; b = i;
        }
        if (dp[i][W] < min_dist){
            min_dist = dp[i][W];
            a = i; b = W;
        }
    }
    cout << min_dist << '\n';

    // 역추적
    vector<int> trace_result;
    for (int i = W; i; i--){

        // 1번 경찰차가 i번 위치에 있다면 i번 사건은 1번 경찰차가 맡게 된 것
        if (a == i){
            trace_result.push_back(1);
            if (b == i - 1){ // 1번 경찰차는 0 ~ i-2번 위치에서 i번 위치로, 2번 경찰차는 i-1번 위치에서 대기
                for (int j = 0; j <= i - 2; j++)
                    if (dp[i][i - 1] == dp[j][i - 1] + (j ? dist(P[j], P[i]) : dist({1, 1}, P[i]))){
                        a = j;
                        break;
                    }
            }
            else a--; // 1번 경찰차는 i-1번 위치에서 i번 위치로, 2번 경찰차는 b번 위치에서 대기
        }

        // 2번 경찰차가 i번 위치에 있다면 i번 사건은 2번 경찰차가 맡게 된 것
        else{
            trace_result.push_back(2);
            if (a == i - 1){ // 1번 경찰차는 i-1번 위치에서 대기, 2번 경찰차는 0 ~ i-2번 위치에서 i번 위치로
                for (int j = 0; j <= i - 2; j++)
                    if (dp[i - 1][i] == dp[i - 1][j] + (j ? dist(P[j], P[i]) : dist({N, N}, P[i]))){
                        b = j;
                        break;
                    }
            }
            else b--; // 1번 경찰차는 a번 위치에서 대기, 2번 경찰차는 i-1번 위치에서 i번 위치로
        }
    }

    while (!trace_result.empty()){
        cout << trace_result.back() << '\n';
        trace_result.pop_back();
    }
}

• Python

import sys; input = sys.stdin.readline
from math import inf

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

N = int(input())
W = int(input())
P = [[(1, 1), (N, N)]] + [tuple(map(int, input().split())) for _ in range(W)] # 경찰차의 처음 위치 + 사건의 위치

dp = [[inf] * (W + 1) for _ in range(W + 1)]
dp[0][0] = 0 # 두 경찰차의 처음 위치에서의 총 이동 거리는 0
dp[1][0] = dist(P[0][0], P[1]) # 경찰차 1번이 1번 사건으로 갔을 때의 이동 거리
dp[0][1] = dist(P[0][1], P[1]) # 경찰차 2번이 1번 사건으로 갔을 때의 이동 거리

for i in range(2, W + 1): # 2번 사건부터 dp 테이블을 채워 나간다.
    for j in range(i - 1):
        # 1번 경찰차는 0 ~ i-2번 위치에서 i번 위치로, 2번 경찰차는 i-1번 위치에서 대기
        dp[i][i - 1] = min(dp[i][i - 1], dp[j][i - 1] + (dist(P[j], P[i]) if j else dist(P[0][0], P[i])))
        # 1번 경찰차는 i-1번 위치에서 대기, 2번 경찰차는 0 ~ i-2번 위치에서 i번 위치로
        dp[i - 1][i] = min(dp[i - 1][i], dp[i - 1][j] + (dist(P[j], P[i]) if j else dist(P[0][1], P[i])))
        # 1번 경찰차는 i-1번 위치에서 i번 위치로, 2번 경찰차는 0 ~ i-2번 위치에서 대기
        dp[i][j] = min(dp[i][j], dp[i - 1][j] + dist(P[i - 1], P[i]))
        # 1번 경찰차는 0 ~ i-2번 위치에서 대기, 2번 경찰차는 i-1번 위치에서 i번 위치로
        dp[j][i] = min(dp[j][i], dp[j][i - 1] + dist(P[i - 1], P[i]))

# 이동 거리가 제일 짧을 때의 두 경찰차의 위치까지 저장
min_dist = inf
for i in range(W):
    if dp[W][i] < min_dist:
        min_dist = dp[W][i]
        a = W; b = i
    if dp[i][W] < min_dist:
        min_dist = dp[i][W]
        a = i; b = W
print(min_dist)

# 역추적
trace_result = []
for i in range(W, 0, -1):

    # 1번 경찰차가 i번 위치에 있다면 i번 사건은 1번 경찰차가 맡게 된 것
    if a == i:
        trace_result.append(1)
        if b == i - 1: # 1번 경찰차는 0 ~ i-2번 위치에서 i번 위치로, 2번 경찰차는 i-1번 위치에서 대기
            for j in range(i - 1):
                if dp[i][i - 1] == dp[j][i - 1] + (dist(P[j], P[i]) if j else dist(P[0][0], P[i])):
                    a = j
                    break
        else: # 1번 경찰차는 i-1번 위치에서 i번 위치로, 2번 경찰차는 b번 위치에서 대기
            a -= 1

    # 2번 경찰차가 i번 위치에 있다면 i번 사건은 2번 경찰차가 맡게 된 것
    else:
        trace_result.append(2)
        if a == i - 1: # 1번 경찰차는 i-1번 위치에서 대기, 2번 경찰차는 0 ~ i-2번 위치에서 i번 위치로
            for j in range(i - 1):
                if dp[i - 1][i] == dp[i - 1][j] + (dist(P[j], P[i]) if j else dist(P[0][1], P[i])):
                    b = j
                    break
        else: # 1번 경찰차는 a번 위치에서 대기, 2번 경찰차는 i-1번 위치에서 i번 위치로
            b -= 1

while trace_result:
    print(trace_result.pop())