취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2618번 문제인 경찰차이다.
문제는 아래 링크를 확인하자.

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

dp[x][y]를 (1번 경찰차가 마지막으로 처리한 사건이 x, 2번 경찰차가 마지막으로 처리한 사건이 y)인 경우의 최소 이동거리라 하자. 이 때 dp값은 이 값은 x>y+1인 경우 dp[x-1][y] + (1번 경찰차가 x-1에서 x까지 이동한 거리), y>x+1인 경우 dp[x][y-1] + (2번 경찰차가 y-1에서 y까지 이동한 거리)로 계산할 수 있다. x=y+1인 경우에는 dp[i][y]의 최솟값(단, i는 y미만), y = x+1인 경우에는 dp[x][i]의 최솟값(단, i는 x 미만)이 된다. x와 y가 같은 경우는 존재할 수 없다.

위의 점화식을 이용해 문제를 해결하자. 어떤 경찰차를 실제로 움직였는지 역추적하는 과정은 위 계산을 진행하면서 각 과정의 최적해가 어떤 이전 단계로부터 왔는지를 별도의 배열에 저장하는 것으로 간단히 구현할 수 있다.

아래는 제출한 소스코드이다.

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

int N, W;
int dp[1001][1001]; // dp[x][y]: 1번 경찰차가 마지막으로 처리한 사건은 x, 2번 경찰차가 마지막으로 처리한 사건은 y
pair<int,int> backtrack[1001][1001];
bool visited[1001][1001];
int R1[1001], C1[1001], R2[1001], C2[1001];

int dist1(int i, int j) {
	return abs(R1[i] - R1[j]) + abs(C1[i] - C1[j]);
}

int dist2(int i, int j) {
	return abs(R2[i] - R2[j]) + abs(C2[i] - C2[j]);
}

int func(int x, int y) {
	int& ret = dp[x][y];
	if (visited[x][y]) return ret;
	visited[x][y] = 1;

	if (x > y + 1) ret = func(x - 1, y) + dist1(x - 1, x), backtrack[x][y] = make_pair(x - 1, y);
	else if (x + 1 < y) ret = func(x, y - 1) + dist2(y - 1, y), backtrack[x][y] = make_pair(x, y - 1);
	else {
		ret = 2000000007;
		if (x > y) {
			for (int i = 0; i < y; i++) {
				int val = func(i, y) + dist1(i, x);
				if (val < ret) ret = val, backtrack[x][y] = make_pair(i, y);
			}
		}
		else {
			for (int i = 0; i < x; i++) {
				int val = func(x, i) + dist2(i, y);
				if (val < ret) ret = val, backtrack[x][y] = make_pair(x, i);
			}
		}
	}

	return ret;
}

int ans = 2000000007, ansx, ansy;
vector<int> stk;

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

	cin >> N >> W;
	for (int i = 1; i <= W; i++) {
		cin >> R1[i] >> C1[i];
	}
	for (int i = 1; i <= W; i++) R2[i] = R1[i], C2[i] = C1[i];
	R1[0] = C1[0] = 1, R2[0] = C2[0] = N;
	
	dp[1][0] = dist1(0, 1), dp[0][1] = dist2(0, 1);
	visited[1][0] = visited[0][1] = 1;
	backtrack[1][0] = backtrack[0][1] = make_pair(0, 0);

	for (int i = 0; i < W; i++) {
		int val = func(i, W);
		if (val < ans) ans = val, ansx = i, ansy = W;
		val = func(W, i);
		if (val < ans) ans = val, ansx = W, ansy = i;
	}
	
	while (ansx + ansy) {
		if (ansx > ansy) stk.emplace_back(1);
		else stk.emplace_back(2);

		int nxtx = backtrack[ansx][ansy].first, nxty = backtrack[ansx][ansy].second;
		ansx = nxtx, ansy = nxty;
	}

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