경찰차

문제 링크

발상

문제 내용을 정리하면 다음과 같다.

2차원 좌표계에서 2개의 말을 움직일 수 있고 주어진 좌표 순서대로 방문시켜야 한다. 각각의 말은 (1,1)과 (N,N)에서 출발하며 목적 좌표에는 어떤 말이 방문하든 상관없다. 2개의 말이 움직이는 거리 합의 최소를 구하라.

문제에서 눈여겨봐야할 중요한 포인트는 좌표를 방문하는 순서는 항상 강제된다는 점이다. 두 경찰차의 위치만 정해지면 다음 좌표까지 방문하는 최소 비용은 자동으로 확정된다. 또한, 그 다음 좌표에서부터는 다음 두 경찰차의 위치가 확정되므로 다다음 좌표까지 방문하는 최소비용도 자동으로 확정된다. 이 재귀 연쇄는 모든 좌표를 방문할 때까지 반복되므로, 우리는 각 단계의 두 경찰차 위치만 알면 나머지 모든 좌표에 방문하는 비용을 확정시킬 수 있다. 이 풀이에서 눈여겨봐야하는 개념은 어느 단계든 두 경찰차의 위치가 확정된다면 이후의 모든 좌표를 방문하는 최소비용까지 확정된다는 것이다. 각 단계에서의 최소비용은 현재 단계의 경찰차를 움직이는 비용 + 움직인 위치에서 나머지 모든 좌표에 방문하는 비용이 된다. 두 경찰차의 위치와 현재 위치 인덱스, 이렇게 3가지 항목이 인자가 된며, 기저 사례는 당연히 마지막 위치를 방문했을 때의 비용, $0$이 된다. 최단거리 DP는 이런 식으로 선택을 했을 때 현재 단계 이후의 모든 최적값이 확정되는 구조의 문제가 많다.

점화식

$$\{\begin{array}{l}{n}_{i,j}=\text{i와 j 위치 인덱스 경찰차가 있을 때 나머지 모든 위치를 방문하는 최소 비용}\\ p=\text{현재 좌표 인덱스}\\ dist(a,b)=\text{위치 인덱스 a와 b 사이의 거리}\end{array}$$ $$n_{i,j}=\min (n_{i,p}+dist(p,j),n_{p,j}+dist(p,i))$$

역추적

점화식의 $n_{i,j}$에 최소 비용과 함께 $i$ 경찰차와 $j$ 경찰차 중 어느 쪽을 선택했을 때 최소 비용이 나왔는지를 함께 저장하면 된다. 첫 인덱스부터 마지막 인덱스까지 선택한 쪽으로 재귀호출을 해나가며 경로를 출력할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
struct pos {
	int x, y;
};
struct node {
	int v, c1, c2, s;
	// v : 최소 비용
	// c1 : 다음 1번 경찰차 위치 인덱스
	// c2 : 다음 2번 경찰차 위치 인덱스
	// s : 1번 경찰차를 선택했는지 2번 경찰차를 선택했는지 여부
};
int n, m;
vector<vector<node>> dp; vector<pos> arr;
 
// 택시 거리 구하는 함수
inline int getdist(pos a, pos b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}
 
//cur : 현재 위치 인덱스
//c1 : 1번 경찰차 위치 인덱스
//c2 : 2번 경찰차 위치 인덱스
node r(int cur, int c1, int c2) {
	if (dp[c1][c2].v != -1) return dp[c1][c2]; // 메모이제이션
	if (cur > m) return dp[c1][c2] = { 0, -1, -1, 0 }; // 기저 사례
 
	//s1 : 1번 경찰차를 골랐을 때 나머지 모든 좌표에 방문하는 최소 비용
	//p1 : 1번 경찰차를 현재 위치 인덱스로 이동시키는 비용
	node s1 = r(cur + 1, cur, c2); int p1 = (c1 == 0 ? getdist({ 1, 1 }, arr[cur]) : getdist(arr[c1], arr[cur]));
 
	//s1 : 2번 경찰차를 골랐을 때 나머지 모든 좌표에 방문하는 최소 비용
	//p1 : 2번 경찰차를 현재 위치 인덱스로 이동시키는 비용
	node s2 = r(cur + 1, c1, cur); int p2 = (c2 == 0 ? getdist({ n, n }, arr[cur]) : getdist(arr[c2], arr[cur]));
 
	// 최소 비용 및 선택을 dp배열에 저장
	return dp[c1][c2] = s1.v + p1 < s2.v + p2 ? node{ s1.v + p1, cur, c2, 1 } : node{ s2.v + p2, c1, cur, 2 };
}
 
//c1 : 1번 경찰차 위치 인덱스
//c2 : 2번 경찰차 위치 인덱스
void printpath(int c1, int c2) {
	if (c1 >= m || c2 >= m) return;
	if (c1 == -1 || c2 == -1) return;
	cout << dp[c1][c2].s << "\n"; // 선택 출력하고 다음 위치로
	printpath(dp[c1][c2].c1, dp[c1][c2].c2);
}
int main() {
	cin >> n >> m; arr = vector<pos>(m + 1); dp = vector<vector<node>>(m + 1, vector<node>(m + 1, { -1, -1 }));
	for (int i = 1; i <= m; i++) {
		cin >> arr[i].x >> arr[i].y;
	}
	auto ret = r(1, 0, 0);
	cout << ret.v << "\n";
	printpath(0, 0);
	return 0;
}