[BAE/<JOON> 문제풀이] 2618. 경찰차 (DP.027)

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

2618번: 경찰차

각각의 사건을 해결 할 때마다 고려해야할 최저수치는 다음과 같다.

 

현재 사건을 n번째 사건이라고 할 때

 

[n-1번 째 사건을 다른 경찰이 해결 했을 때의 비용보다 현재 경찰이 해결하는 비용이 더 적은가?]

 

우선 점화식을 도출해낸 과정은 다음과 같다.

 

n번째 사건까지의 최솟값과 n + 1번째 사건까지의 최솟값 사이에 관계가 없다.

 

왜냐하면 n + 1 번째 사건 위치에 따라서 n번까지의 경로가 모두 바뀔 수 있기 때문이다.

 

따라서 보통 사용하는 1차 배열에 각각의 단계에 대한 최솟값을 넣어놓고 정답을 구하는 방식으로는 

 

답을 도출 할 수 없다고 생각했다. ( 이걸 모르고 짠 여러가지 실패작들이 많다... )

 

따라서 모든 x, y쌍에 대한 값을 저장해야겠다고 판단을 하여

 

{ dp[x][y] = 현재 사건까지의 최솟값 } 으로 정하였다.

 

이러면 각각의 사건에 대해서 x, y번째 까지 1번, 2번 경찰차가 해결 했다고 놓았을 때,

다음 사건, 즉 x, y중 큰 값 + 1 번째 사건을  각각 1번, 2번 경찰차에 맡겼을 경우들을 검사하면 최솟값을 찾을 수 있다.

 

이런식으로 사건을 하나씩 해결해가다가 마지막 사건에 도착하면 호출 트리를 거슬러 올라가며 비용들을 합산한다.

 

arr : 사건 좌표 배열
dp : 테이블용 배열
rg() : 두 좌표사이의 최소거리 반환

int case_engage(int x, int y) {
 	if (x >= n || y >= n) return 0;//마지막 사건이면 탐색을 종료하고 반환
	int nc = x > y ? x : y;
	nc += 1;//next case
	
    //다음 사건에 첫번째 경찰차가 가는 경우
	int nx = case_engage(nc, y) + rg(arr[nc], arr[x]); //다음 사건까지의 거리 + 다음 사건에서의 최솟값
    
    //다음 사건에 두번째 경찰차가 가는 경우
	int ny = case_engage(x, nc) + rg(arr[nc], arr[y]);

	return dp[x][y] = nx < ny ? nx : ny;//최솟값으로 갱신
}

 

위 코드처럼 첫 설계를 할 수 있다.

 

해당 로직으로 코딩을 하여 제출을 하면 시간 초과가 발생한다. 현재 모든 노드를 탐색하고 호출 함수로 되돌아 오며 

 

값을 계산하는 바텀업 방식이며 방문해야하는 사건 발생지는 정해져있기 때문에 한번 초기화된 노드는 다시 탐색할 필요가 없다.

 

arr : 사건 좌표 배열
dp : 테이블용 배열
rg() : 두 좌표사이의 최소거리 반환

함수 호출 전, dp배열 -1로 초기화

int case_engage(int x, int y) {
 	if (x >= n || y >= n) return 0;//마지막 사건이면 탐색을 종료하고 반환
	int nc = x > y ? x : y;
	nc += 1;//next case
    
    if(dp[x][y] != -1) return dp[x][y];//이미 값이 들어가 있다면 해당 값 반환
	
    //다음 사건에 첫번째 경찰차가 가는 경우
	int nx = case_engage(nc, y) + rg(arr[nc], arr[x]); //다음 사건까지의 거리 + 다음 사건에서의 최솟값
    
    //다음 사건에 두번째 경찰차가 가는 경우
	int ny = case_engage(x, nc) + rg(arr[nc], arr[y]);	

	return dp[x][y] = nx < ny ? nx : ny;//최솟값으로 갱신
}

 

이렇게 최댓값을 찾는 로직을 완료하고 두번 째로 갔던 길들을 찾아줘야된다.

 

처음에 단순하게 생각했을 때는 [최댓값 찾는 로직에서 nx, ny를 고르는 부분에서 nx를 고르면 1, ny를 고르면 2]

 

이것도 잘못된 걸 생각해내는게 너무 어려웠다. 

 

[ 탐색을 하며 최적값이 마지막으로 탐색되지 않고 가장 먼저 탐색되면 뒤따라오는 탐색들로 인해서

 

같은 사건번호에 최적값이 아닌 다른 값이 씌워지기 때문이다. ]

 

 

 

그래서 탐색을 완료 한 뒤, dp배열을 복기하며 최적 경로를 탐색하는 루틴을 하나 재작성 할  필요가 있다.

 

이 부분의 로직은 위의 최소값을 찾는 루틴을 그대로 돌리되, 양방향으로 탐색한 값은 dp배열에 그대로 남아있으므로,

 

양 방향 중, 다음 사건까지의 거리가 가까운 쪽을 골라주면 된다.

 

void case_track(int x, int y) {
	if (x >= w + 1 || y >= w + 1) return;//all case closed 끝까지 탐색하면 복귀
	int nc = x > y ? x : y;
	nc += 1;//next case	
	int nx = rg(arr[nc], arr[x]); //다음 지점까지의 거리
	int ny = rg(arr[nc], arr[y]);

	if (dp[nc][y] + nx < dp[x][nc] + ny) { //현재까지의 거리 + 다음 지점까지의 거리 중 작은 방향 선택
		cout << 1 << "\n";
		case_track(nc, y); // 다음 사건 지점 추적
	}
	else {
		cout << 2 << "\n";
		case_track(x, nc);
	}
	return;
}

 

거의 이틀동안 이 문제만 풀었다.

 

이게 정올 중등부 문제라는데, 그럼 이걸 대회에서는 3~4시간안에 도출해내야 된다는건가... 세상에..

 

그동안 푼 DP 문제 중 제일 어려웠다 진짜

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct c {
	int x, y;
};

int rg(c c1, c c2) {
	return abs(c1.x - c2.x) + abs(c1.y - c2.y);
}

int n, w;
vector<vector<int>> dp;
vector<int> path;
vector<c> arr;

int case_engage(int x, int y) {
 	if (x >= w + 1 || y >= w + 1) return 0;//all case closed
	int nc = x > y ? x : y;
	nc += 1;//next case

	//memo::이미 각 경찰차가 현재 x, y번째 사건을 방문 한적이 있다면 최솟값이 갱신된것임
	if (dp[x][y] > -1) return dp[x][y];
	/*dp[x][y] = dp[x][y] < dp[nc][y] + rg(arr[nc], arr[x]) ? dp[x][y] : dp[nc][y] + rg(arr[nc], arr[x]);
	dp[x][y] = dp[x][y] < dp[x][nc] + rg(arr[nc], arr[y]) ? dp[x][y] : dp[x][nc] + rg(arr[nc], arr[y]);*/
	//최솟값 갱신
	int nx = case_engage(nc, y) + rg(arr[nc], arr[x]); //다음 사건까지의 거리 + 다음 사건에서의 최솟값
	int ny = case_engage(x, nc) + rg(arr[nc], arr[y]);		

	return dp[x][y] = nx < ny ? nx : ny;
}

void case_track(int x, int y) {
	if (x >= w + 1 || y >= w + 1) return;//all case closed
	int nc = x > y ? x : y;
	nc += 1;//next case	
	int nx = rg(arr[nc], arr[x]); //다음 사건까지의 거리 + 다음 사건에서의 최솟값
	int ny = rg(arr[nc], arr[y]);

	if (dp[nc][y] + nx < dp[x][nc] + ny) {
		cout << 1 << "\n";
		case_track(nc, y);
	}
	else {
		cout << 2 << "\n";
		case_track(x, nc);
	}
	return;
}

int main() {
	cin >> n >> w;
	arr.resize(w + 2);
	dp.resize(w + 2);
	path.resize(w + 1);
	arr[0] = { 1, 1 };
	arr[1] = { n, n };
	dp[0].resize(w + 2);
	dp[1].resize(w + 2);
	for (int i = 2; i <= w + 1; i++) {
		cin >> arr[i].x >> arr[i].y;
		dp[i].resize(w + 2);
	}

	for (int i = 0; i <= w + 1; i++) {
		for (int j = 0; j <= w + 1; j++) {
			dp[i][j] = -1;
		}
	}

	//0, 1번지의 각각의 경찰자 출동지를 집어넣고 돌리므로 사건 번호는 0~w+1까지다.
	cout << case_engage(0, 1) << endl;
	/*for (int i = 0; i <= w + 1; i++) {
		for (int j = 0; j <= w + 1; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	case_track(0, 1);
	return 0;
}