[알고리즘] 백준 2618 경찰차

이희수·2024년 8월 21일

C++DP 백준 2618 알고리즘

알고리즘

목록 보기

20/25

📖문제

2618 경찰차

💡구상

사건이 최대 1000번 일어날 수 있고, 경찰차는 2대가 있으니 단순히 완전탐색으로 풀려면 2^1000 의 경우의 수를 탐색해야한다.

그럼 DP로 접근해보자.

제일 처음에 든 생각은 각 경찰차의 좌표를 DP배열에 넣는 것이었다.

하지만 도시의 크기는 최대 1000x1000 이므로 경찰차의 좌표를 가진 DP 배열을 만들려면 최소 1000X1000X1000X1000 의 공간복잡도가 필요하기 때문에, 만들수 없다.

int DP[경찰차1.Y][경찰차1.X][경찰차2.Y][경찰차2.X];

또한 이 문제는 경찰차가 선택한 선택지를 Trace 해야하기 때문에 고려사항이 많다.

코드를 보며 살펴보자.

🔍코드

#include<bits/stdc++.h> 
using namespace std;
int n,w;
int y[1004],x[1004];
int dp[1004][1004];
// 거리 계산 
int cal(int a,int b){
	return abs(y[a]-y[b])+abs(x[a]-x[b]);
}
// DP
int go(int a, int b){
	if(a==w+1 || b==w+1) return 0;
	
	int &ret = dp[a][b];
	if(ret) return ret;
	
	int next = max(a,b)+1;
	ret = min(go(next,b)+cal(a,next), go(a,next)+cal(b,next));
	return ret;
}
int main(){
	cin>>n>>w;
	// 경찰차1,2 좌표 초기화 
	y[0]=1, x[0]=1;
	y[1]=n, x[1]=n;
	for(int i=2; i<=w+1; i++){
		cin>>y[i]>>x[i];
	}
	cout<<go(0,1)<<"\n";
	// Trace 
	int a=0, b=1;
	for(int i=2; i<=w+1; i++){
		if(dp[i][b]+cal(a,i) < dp[a][i]+cal(b,i)){
			cout<<"1\n";
			a=i;
		}
		else{
			cout<<"2\n";
			b=i;
		}
	}
 	return 0;
}

DP배열

앞서 말했듯이, DP배열의 파라미터로 좌표를 모두 넣을 수 없다. 그렇다면 Index를 이용해보자.

0번 Index를 경찰차1, 1번 Index를 경찰차2, 2번 Index를 사건1 ... 이런식으로 Index를 할당한 후 각 좌표를 Y,X 배열에 저장해 놓으면, 1000*1000의 공간복잡도로 DP배열을 만들 수 있다.

int go(int a, int b){
	if(a==w+1 || b==w+1) return 0;
	
	int &ret = dp[a][b];
	if(ret) return ret;
	
	int next = max(a,b)+1;
	ret = min(go(next,b)+cal(a,next), go(a,next)+cal(b,next));
	return ret;
}

위 함수에서 a는 경찰차1, b는 경찰차2를 뜻한다. 움직였을때 최솟값이 되는 경찰차로 할당하며 탐색을 마지막 사건이 될때까지 진행해나간다.

int next = max(a,b)+1;

다음 목적지는 다음 Index로 할당하기 위해 최댓값+1로 설정한다. ex) (0,1) -> next: 2

Trace

이제 어떤 사건에 어떤 경찰차가 배정되었는지 다시 추적하는 과정이 필요하다.

이는 우리가 DP배열을 갱신하는 과정을 역으로 생각해보아야 한다.

// Trace 
	int a=0, b=1;
	for(int i=2; i<=w+1; i++){
		if(dp[i][b]+cal(a,i) < dp[a][i]+cal(b,i)){
			cout<<"1\n";
			a=i;
		}
		else{
			cout<<"2\n";
			b=i;
		}
	}

dp[0][1] 에는 모든 탐색을 끝냈을때의 최솟값이 들어있을 것이다. 즉 dp[0][1]은 dp[2][1]+cal(0,2) 와 dp[0][2]+cal(1,2)의 값중 작은 값이 들어있는 것이다.
그래서 두 값을 비교하여 작은쪽으로 이동한 것이므로 두 값을 비교해나가며 a,b 값을 갱신해가면 추적이 가능하다.