Problem

Solution

• 처음에는 최소 거리의 경찰차만을 선택하는 Greedy 알고리즘으로 문제를 해결할 수 있을 것으로 생각하였다. 하지만 그리디 알고리즘으로는 거리의 합의 최솟값을 얻을 수 없었다.
• 완전탐색을 적용하돼 Dynamic Programming을 통해서 시간 내에 문제를 해결할 수 있다.
• 다음은 시행착오를 겪은 Memoization을 적용할 Solve 함수의 매개변수 목록이다.

  Ⅰ) [ i ][ n ] : i번째 사건(1~N), n번째 경찰차(1~2)
  → 경찰차의 좌표가 다르면 다른 경우의 수
  Ⅱ) [ x1 ][ y1 ][ x2 ][ y2 ] : 경찰차들의 좌표
  → 시간 초과가 나게 되며 배열이 sparse함
  Ⅲ) [ n1 ][ n2 ] : 첫 번째, 두 번째 경찰차가 마지막으로 맡은 n1, n2번째 사건

• 거리의 최솟값 뿐만 아니라 각 사건별로 어떤 경찰차가 맡았는 지를 출력해야 하기 때문에
  Reconstruct 함수를 구상해야 한다. cache 배열은 모든 경우의 수에 대한 거리의 합을 저장하고 있다. 첫 번째 사건에서 경찰차1을 선택했을 때의 cache값과 경찰차2를 선택했을 때의 cache값을 비교하여 어느 경찰차를 선택했는 지 알 수 있다. 이를 N번째 사건까지 반복한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
using namespace std;
const int MIN = 20000000;

int N, W;
int cases[1003][2];
int cache[1003][1003];

int Distance(pair<int, int> cPrev, pair<int, int> cNext){
	return abs(cNext.first - cPrev.first) + abs(cNext.second - cPrev.second);
}
/* 
 첫번째 경찰차가 맡은 사건: a 번째 사건
 두번째 경찰차가 맡은 사건: b 번째 사건
 i번째 사건을 처리해야한다
*/
int Solve(int a, int b, int i){
	int num;
	int& ret = cache[a][b];
	// 기저조건
	if(i == W+1){
		// 마지막 사건의 좌표
		int nx = cases[i][0], ny = cases[i][1];
		// 첫번째 경찰차의 좌표
		int fx = cases[a][0], fy = cases[a][1];
		// 첫번째 경찰차가 맡았을 때의 거리
		int fdist = Distance({fx,fy},{nx,ny});
		// 두번째 경찰차의 좌표
		int sx = cases[b][0], sy = cases[b][1];
		// 두번째 경찰차가 맡았을 때의 거리
		int sdist = Distance({sx,sy},{nx,ny});
		
		ret = min(fdist, sdist);
		
		return ret;
	}
	
	if(ret != MIN) return ret;
	// i번째 사건의 좌표
	int nx = cases[i][0], ny = cases[i][1];
	// 첫번째 경찰차
	int fx = cases[a][0], fy = cases[a][1];
	int fdist = Distance({fx, fy}, {nx, ny});
	// 두번째 경찰차
	int sx = cases[b][0], sy = cases[b][1];
	int sdist = Distance({sx, sy}, {nx, ny});
	
	// 첫번째 경찰차의 경우의 수
	ret = min(ret, fdist + Solve(i, b, i+1));
	// 두번째 경찰차의 경우의 수
	ret = min(ret, sdist + Solve(a, i, i+1));
	
	return ret;
}

void Reconstruct(int a, int b, int i){
	if(i == W+1){
		int nx = cases[i][0], ny = cases[i][1];
		int x, y, dist;
		// 첫번째 경찰차 좌표
		x = cases[a][0], y = cases[a][1];
		dist = Distance({x, y}, {nx, ny});
		// 두번째 경찰차의 좌표는 고려할 필요가 없다.
		if(dist == cache[a][b]) printf("%d \n", 1);
		else printf("%d \n", 2);
		
		return;
	}
	// i번째 사건의 좌표
	int nx = cases[i][0], ny = cases[i][1];
	int x, y, dist, cacheDist;
	// 첫번째 경찰차 좌표
	x = cases[a][0], y = cases[a][1];
	dist = Distance({x, y}, {nx, ny});
	// 첫번째 경찰차를 선택했을 때의 cache값 차이
	cacheDist = cache[a][b] - cache[i][b];
	
	if(dist[0] == cacheDist[0]){
		printf("%d \n", 1);
		Reconstruct(i, b, i+1);
	}
	else{
		printf("%d \n", 2);
		Reconstruct(a, i, i+1);
	}
}

int main(){
	scanf("%d", &N);
	scanf("%d", &W);
	for(int i=2; i<W+2; i++)
		scanf("%d %d", &cases[i][0], &cases[i][1]);
	// 경찰차의 초기 위치를 사건의 위치로 저장한다
	cases[0][0] = 1; cases[0][1] = 1;
	cases[1][0] = N; cases[1][1] = N;
	
	fill(&cache[0][0], &cache[1002][1003], MIN);
	// cases[2]부터 첫번째 사건이 저장되어있다
	int mins = Solve(0, 1, 2);
	
	printf("%d \n", mins);
	
	Reconstruct(0, 1, 2);
}

Result