[백준/BOJ] 백준 2618번 : 경찰차

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

2618번: 경찰차

int Solve(int police1_last, int police2_last) (police1_last는 경찰차1이 마지막으로 처리한 사건, police2_last는 경찰차2가 마지막으로 처리한 사건)으로 그때 최소 이동거리를 다이나믹 프로그래밍을 이용해 구하고, Police_check(int police1_last, int police2_last) (police1_last는 경찰차1이 마지막으로 처리한 사건, police2_last는 경찰차2가 마지막으로 처리한 사건)으로 Solve에서 만든 cache[][]를 이용해 어떤 경찰차가 해결했는지 구한다.

 

코드

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

int n;
int w;
vector<pair<int, int>> point;
int cache[1001][1001];
vector<int> check;

void Pre()
{
	for (int i = 0; i < 1001; i++)
		for (int j = 0; j < 1001; j++)
			cache[i][j] = -1;
}

int Solve(int police1_last, int police2_last)
{
	int& ret = cache[police1_last][police2_last];

	if (ret != -1)
		return ret;

	//경찰차1이나 경찰차2가 마지막 사건을 처리했을경우
	if (police1_last == w || police2_last == w)
		return 0;

	//지금 처리할 사건
	int solve_point_index = max(police1_last, police2_last) + 1;

	//처리할 위치
	pair<int, int> solve_point = point[solve_point_index];

	pair<int, int> police1_point; //현재 경찰차1의 위치
	int police1_len;//해당 위치를 경찰차1이 처리할 경우 거리

	pair<int, int> police2_point; //현재 경찰차2의 위치
	int police2_len;//해당 위치를 경찰차2가 처리할 경우 거리

	if (police1_last == 0)
		police1_point = make_pair(1, 1);
	else
		police1_point = point[police1_last];

	if (police2_last == 0)
		police2_point = make_pair(n, n);
	else
		police2_point = point[police2_last];

	police1_len = abs(solve_point.first - police1_point.first) + abs(solve_point.second - police1_point.second);
	police2_len = abs(solve_point.first - police2_point.first) + abs(solve_point.second - police2_point.second);

	//결과가 경찰차1이 처리할때와 경찰차2가 처리할때 중 작은것을 고른다
	ret = min(police1_len + Solve(solve_point_index, police2_last), police2_len + Solve(police1_last, solve_point_index));

	return ret;
}

void Police_check(int police1_last, int police2_last)
{
	if (police1_last == w || police2_last == w)
		return;

	//다음 사건
	int solve_point_index = max(police1_last, police2_last) + 1;

	//처리할 위치
	pair<int, int> solve_point = point[solve_point_index];

	pair<int, int> police1_point; //현재 경찰차1의 위치
	int police1_len;//해당 위치를 경찰차1이 처리할 경우 거리

	pair<int, int> police2_point; //현재 경찰차2의 위치
	int police2_len;//해당 위치를 경찰차2가 처리할 경우 거리

	if (police1_last == 0)
		police1_point = make_pair(1, 1);
	else
		police1_point = point[police1_last];

	if (police2_last == 0)
		police2_point = make_pair(n, n);
	else
		police2_point = point[police2_last];

	police1_len = abs(solve_point.first - police1_point.first) + abs(solve_point.second - police1_point.second);
	police2_len = abs(solve_point.first - police2_point.first) + abs(solve_point.second - police2_point.second);

	//경찰차1이 해결하는게 더 짧은 결과값일때
	if (cache[solve_point_index][police2_last] + police1_len < cache[police1_last][solve_point_index] + police2_len)
	{
		check.push_back(1);
		Police_check(solve_point_index, police2_last);
	}

	else
	{
		check.push_back(2);
		Police_check(police1_last, solve_point_index);
	}
}

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

	Pre();

	cin >> n;
	cin >> w;

	//실제 사건은 1번 인덱스부터 넣기 위해 point에 임의로 하나 넣어둔다
	point.push_back(make_pair(-1, -1));

	for (int i = 0; i < w; i++)
	{
		int x, y;
		cin >> x >> y;

		point.push_back(make_pair(x, y));
	}

	cout << Solve(0, 0) << "\n";

	Police_check(0, 0);

	for (int i = 0; i < check.size(); i++)
		cout << check[i] << "\n";

	return 0;
}