백준, boj) 2618. 경찰차 ( C / C++)

1. 문제 링크

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

2618번: 경찰차

 

2. 문제 개요

도시가 NxN으로 이루어져 있고 각각 동서방향 도로 N개와 남북방향 N개의 도로로 이루어져 있다.

도로 사이의 모든 거리는 1이다.

경찰차 1, 경찰차 2가 (1,1) (n, n)의 위치에 있다. 처리할 사건이 있으면 그 사건이 발생된 위치를 두 대의 경찰차 중 하나에 알려주고, 연락받은 경찰차는 그 위치로 가낭 자른 길을 통해 이동하여 사건을 처리한다.

두대의 경찰차들이 이동하는 거리의 합을 최소화 하도록 사건을 맡길 때, 거리의 합과 각 사건을 처리한 경찰차의 번호를 출력하자.

 

 

3. 문제 힌트

결국에 최단거리를 만드는것은 완전 탐색이다.

그런데 dp를 사용하여 시간 복잡도를 줄이는 것.

 

그럼 dp를 어떻게 설계해야 할까?

dp [i][j]를 둬보자. i는 1번 경찰차가 마지막으로 처리한 사건번호. j는 2번 경찰차가 마지막으로 처리한 사건번호이다.

 

그럼 i , j 중 가장 큰 번호의 +1이 다음에 처리할 사건번호가 된다. -> max(i, j) + 1 : 다음 사건 번호.

 

그리고 dp[i][j]를 1번 경찰차가 마지막으로 i, 2번 경찰차가 마지막으로 j사건을 처리했을 때, 앞으로 가야 할 이동거리'이라고 가정하자.

 

왜냐하면 '이때까지 이동한 이동거리'라고 두면

dp[마지막사건][0~마지막사건-1] 아니면 dp[0~마지막사건-1][마지막사건] 중 최솟값이 답이 되는데, 이러면 너무 복잡해지고 답을 찾기 어렵다.

 

dp[0][0]를 찾는 것이 이 문제의 핵심이다. 

 

 

4. 문제 풀이

 

(3) 번에서 적었듯이, dp를 (3) 번과 같이 정의하자.

 

그럼

Next = max(i, j) +1이 된다. (다음에 처리해야 할 사건번호 = 지금까지 처리한 사건번호 중 최댓값 +1)

 

결국엔 완전 탐색이라고 했다.

그런데 dp를 사용해서 시간 복잡도를 줄이는 것.

 

최초 시작점에서 1번 경찰차를 출동시켜보고 2번 경찰차를 출동시켜봐야 한다.

즉, Next를 구했을 때,

 

dp[x][y] = min(dp[next][y] + dist1, dp[x][next] + dist2)가 된다.

 

여기서 dist1, dist2는 경찰차를 출동시켰을 때 이동하는 거리가 되고,

dp[x][y] = dp[next][y] + dist1을 예로 들었을 때,

경찰차 1번은 x번째 사건이 일어났던 위치에 있다. 그런데 이게 next번째 사건으로 이동하는 것이다.

따라서 x번째 사건과 next번째 사건의 거리가 dist1이 된다.

dist2도 이처럼 구해주자.

 

그렇게 이게 재귀적으로 모두 탐색하면서 최솟값을 구하는 것이다.

 

 

자, 최솟값은 구했다.

그럼 경로는 어떻게 구할까?

초기값인 dp_table[0][0]에는 최솟값까지의 남은 거리를 저장해놓는다. 따라서 초기값부터 dp_table을 이용해서 직접 움직여보고, (1번 경찰차를 출동시켜보고, 2번 경찰차도 출동시켜보고)

작은 값을 계속 취하면 된다. 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

int n,w;

pair<int, int> work[1001];
int dp_table[1001][1001];

int dist(pair<int, int>a, pair<int, int>b)
{
	return abs(b.first - a.first) + abs(b.second - a.second);
}


int dp(int x, int y)
{
	if (x == w || y == w)
		return 0;

	//memoization
	int &cache = dp_table[x][y];
	if (cache != -1)	return dp_table[x][y];

	int next = max(x, y) + 1;	//다음사건
	int dist1, dist2;
	
	//base
	//x가 next로 움직일때,
	if (x == 0)
		dist1 = dist({ 1,1 }, work[next]);
	else
		dist1 = dist(work[x],work[next]);

	//y가 next로 움직일때
	if (y == 0)
		dist2 = dist({ n,n }, work[next]);
	else
		dist2 = dist(work[y], work[next]);

	cache = min(dp(next, y) + dist1, dp(x, next) + dist2);
	return cache;
}

void tracert(int x, int y)
{
	if (x == w || y == w)
		return;

	int next = max(x, y) + 1;	//다음사건
	int dist1, dist2;

	//base
	//x가 next로 움직일때,
	if (x == 0)
		dist1 = dist({ 1,1 }, work[next]);
	else
		dist1 = dist(work[x], work[next]);

	//y가 next로 움직일때
	if (y == 0)
		dist2 = dist({ n,n }, work[next]);
	else
		dist2 = dist(work[y], work[next]);

	if (dp_table[next][y] + dist1 > dp_table[x][next] + dist2) {
		printf("2\n");
		tracert(x, next);
	}
	else
	{
		printf("1\n");
		tracert(next, y);
	}

	return;
}
int main()
{
	scanf("%d", &n);
	scanf("%d", &w);
	for (int i = 1; i <= w; ++i) 
		scanf("%d %d", &work[i].first, &work[i].second);
	memset(dp_table, -1, sizeof(dp_table));

	printf("%d\n", dp(0, 0));
	tracert(0, 0);
	

	return 0;
}

6. 결과 사진

dp를 남은 거리라고 안 하고 계속 이동한 거리로 두고 풀어서 너무 복잡해서 힘들었다.

생각의 전환을 해볼 수 있는 좋은 문제였다.

 

지적, 댓글 언제나 환영입니다~