[백준] No.2618 - 경찰차 (C++)

문제

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

2618번: 경찰차

 

풀이

solved.ac 난이도: Platinum-5

 

최단 이동 거리를 구하는 것과 어느 순서대로 경찰차를 이동시켜야 최단 이동 거리가 나오는지까지 구해야 하는 문제.

 

일단 최단 이동 거리를 구하는 재귀함수부터 구현해보자.

 

int MovePatrolCar(int incident_idx,int patrol1_pos, int patrol2_pos )

incident_idx번째 사건을 경찰차1가 해결할 때의 최단거리, 경찰차2가 해결할때의 최단거리를 반환하는 재귀함수이다.  

 

patrol1_pos은 경찰차1가 마지막으로 해결한 사건의 번호

patrol2_pos은 경찰차2가 마지막으로 해결한 사건의 번호를 각각 나타낸다.

 

해당 문제를 해결할 때 각 사건의 위치(r,c)로 직접 경찰차의 위치를 나타낼 수도 있겠지만,

해당 경찰차가 마지막으로 해결한 사건의 번호만 안다면 각 사건의 위치를 저장해둔 vector<pair<int,int>> incident_list에서 해당 위치값을 가져올 수 있으므로 사건의 번호만으로 연산을 진행하여 메모이제이션의 메모리를 절약할 수 있다.

 

따라서 dp[patrol1_pos][patrol1_pos]만으로 각 차량이 해당 위치일 때의 최솟값을 저장할 수 있다.

 

본인의 경우, 3차원 배열 dp[incident_idx][patrol1_pos][patrol2_pos]를 이용하여 해당 사건(incident_idx)을 어떤 경찰차가 해결하는지 저장하려 했지만 메모리 제한을 초과하였다.

그 이유는,  incident_idx =3 즉, 3번째 사건을 해결하는 값을 저장한다고 생각했을 때 가능한 patrol1_pos와 patrol2_pos의 값은 (1,3), (2,3), (3,1), (3,2)이다.

 

모든 결과에서 patrol1_pos와 patrol2_pos 둘 중 하나의 값이 3일 수밖에 없다.

결과적으로 incident_idx가 어떤 값이든 해당 사건을 해결하는 경찰차는 필요하므로 patrol1_pos와 patrol2_pos 둘 중 하나의 값이 된다.

따라서 dp[incident_idx]는 어떤 정보도 제공해주지 않는, 메모리 낭비이다. 

 

이제 두 가지 경우 중 작은 경로를 선택하면 된다.

 

1. 경찰차1이 해당 사건을 해결하는 경우

patrol1_pos와 해당 사건의 거리 + MovePatrolCar(incident_idx+1, incident_idx,  patrol2_pos )

여기서 다음 재귀호출시 patrol1_pos는 해당 사건을 해결했으므로 incident_idx로 넘겨주자.

 

2. 경찰차2이 해당 사건을 해결하는 경우

patrol2_pos와 해당 사건의 거리 + MovePatrolCar(incident_idx+1, patrol1_pos,  incident_idx )

 

두 경우 중 더 큰 값이 dp[patrol1_pos][patrol1_pos] 의 값이 된다.

 

마지막으로 해당 사건을 해결하는 경찰차 번호 출력을 구현하자.

다시 이동 거리 값을 계산하여 최솟값으로만 이동하는 재귀함수를 구현할 수도 있지만, 본인은 단순히 아래와 같이 해결했다.

dp[patrol1_pos][patrol1_pos][2]를 추가하여

최단 이동 거리의 값은 dp[patrol1_pos][patrol1_pos][0]에 , 그때 선택한 경찰차 번호는 dp[patrol1_pos][patrol1_pos][1]에 저장하면 dp[patrol1_pos][patrol1_pos][1]만 따라가도 선택한 경찰차 번호를 구할 수 있다.

 

참고로 경찰차1,2의 시작 위치는 incident_list[0],[1]에 각각 저장하여 incident_idx를 2부터 시작하면 추가적으로 patrol_pos값이 시작 위치인지 확인할 필요가 없어진다.

코드