[BeakJoon 2618] 경찰차

안녕하세요. 이번 포스팅에서는 백준 2618번 경찰차 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

2618번: 경찰차

 

위 링크에서 확인하실 수 있습니다.

 

우선 이 문제는 굉장히 어려운 문제입니다. 그 이유는 문제의 제한입니다.

 

보통 이런 문제는 

int go(int orderIdx, int firstCar, int secondCar) {
	if(orderIdx == w) return 0;
	
	int& ret = dp[orderIdx][firstCar][secondCar]
	if(ret) return ret;
	ret = 1e9;
	
	int ret1 = go(orderIdx+1, orderIdx, secondCar) + getDist(firstCar, orderIdx);
	int ret2 = go(orderIdx+1, firstCar, orderIdx]) + getDist(secondCar, orderIdx);
	
	if(ret1 < ret2) {
		_select[orderIdx] = 1; 
	} else _select[orderIdx] = 2;
	
	return ret = min(ret1, ret2);
}

 

이런 풀이를 떠올리실 수 있습니다. 쉽게 설명하자면, 

 

현재 orderIdx에서 첫 번째 차로 얻는 최솟값 vs 두 번째 차로 얻는 최솟값을 비교하여 최솟값을 저장하는 형태입니다. 이 풀이로 하시면 dp배열이 문제의 인풋에 따라서

 

1000*1000*1000의 dp배열이 필요합니다. 당연히 선언할 수 없습니다.

 

따라서 orderIdx를 사용하지 않고 orderIdx를 얻어내야 합니다. 

 

이전 함수에서 어차피 firstCar와 secondCar 둘중 하나는 이전 orderIdx라는 점을 유의 깊게 보시면 다음 재귀 함수에서 orderIdx를 max(firstCar, secondCar) + 1을 통해 얻을 수 있다는 것을 알 수 있습니다.

 

어차피 인풋으로 orders값이 다 저장된 배열을 가지고 있기 때문에, firstCar, secondCar 모두 인덱스의 형태로 갖고있으면, 더 나중의 인덱스가 선택될 것이기 때문입니다.

 

따라서 위의 코드는 다음과 같이 인풋 배열을 줄이고도 정상적으로 결과를 도출할 수 있습니다.

int go(int firstCar, int secondCar) {
	
	int orderIdx = max(firstCar, secondCar)+1;
	if(orderIdx == w+1) return 0;
	
	int& ret = dp[firstCar][secondCar];
	if(~ret) return ret;
	
	ret=1e9;
	int ret1 = go(orderIdx, secondCar) + getDist(firstCar, orderIdx);	 	
	int ret2 = go(firstCar, orderIdx) + getDist(orderIdx, secondCar);
	
	if(ret1 < ret2) {
		ret=ret1; _select[firstCar][secondCar]=1;
	} else {
		ret=ret2; _select[firstCar][secondCar]=2;
	}
	return ret;
}

 

이제 경로를 어떻게 출력하는지 살펴 보겠습니다.

 

경로는 _select[firstCar][secondCar]에 결과로 선택하는 경찰차의 번호를 넣어 주었습니다. 그리고 출력할 때 알고리즘과 마찬가지로 x y값을 각각 max를 통해 변경해주며 출력해주었습니다.

 

아래는 전체 소스코드입니다.

 

<소스 코드>

#include<bits/stdc++.h>
using namespace std; 
int n, w, res = 1e9, _select[1004][1004], dp[1004][1004];
pair<int,int> orders[1004];
int getDist(int here, int next) {
	pair<int,int> car = orders[here], goal = orders[next];
	if(here==0) car={1,1}; 
	if(next==0) goal={n,n};
	return (abs(car.first - goal.first) + abs(car.second - goal.second));
}
int go(int firstCar, int secondCar) {
	
	int orderIdx = max(firstCar, secondCar)+1;
	if(orderIdx == w+1) return 0;
	
	int& ret = dp[firstCar][secondCar];
	if(~ret) return ret;
	
	ret=1e9;
	int ret1 = go(orderIdx, secondCar) + getDist(firstCar, orderIdx);	 	
	int ret2 = go(firstCar, orderIdx) + getDist(orderIdx, secondCar);
	
	if(ret1 < ret2) {
		ret=ret1; _select[firstCar][secondCar]=1;
	} else {
		ret=ret2; _select[firstCar][secondCar]=2;
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> w;
	for(int i = 1; i <= w; i++) {
		int a, b; cin >> a >> b;
		orders[i] = {a,b};
	}
	
	fill(&dp[0][0], &dp[0][0]+1004*1004, -1);
	
	res = go(0, 0);
	cout << res << "\n";
	
	int x=0, y=0;
	while(1) {
		cout << _select[x][y] << "\n";
		if(_select[x][y]==2) y=max(x,y)+1;
		else x=max(x,y)+1;
		
		if(max(x,y)==w) break;	
	}
	return 0; 
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.