이번에는 백준 2618번 경찰차 문제를 풀어보았습니다.
처음에는 어떤 경찰차를 보내야 할지 매 순간 선택하는 그리디 문제처럼 보였지만, 현재 두 경찰차의 위치에 따라 이후 최적의 선택이 달라지기 때문에 그리디로는 해결할 수 없는 문제였습니다.
현재 두 경찰차가 마지막으로 처리한 사건만 알면 이후 최소 이동 거리를 구할 수 있으므로 DP(메모이제이션) 를 이용하여 해결하였습니다.
문제 설명
두 대의 경찰차가 있습니다.
- 경찰차 1의 시작 위치는
(1,1) - 경찰차 2의 시작 위치는
(N,N)
사건이 순서대로 발생하며,
각 사건은 두 경찰차 중 한 대가 반드시 처리해야 합니다.
모든 사건을 처리했을 때 두 경찰차의 총 이동 거리의 최솟값을 구하고,
각 사건을 어떤 경찰차가 처리했는지도 출력해야 합니다.
풀이 아이디어
현재 상태를
- 경찰차 1이 마지막으로 처리한 사건
- 경찰차 2가 마지막으로 처리한 사건
으로 정의하였습니다.
다음 사건은 항상
max(a, b) + 1번째 사건이 되므로,
현재 상태만 알면 이후 최소 이동 거리를 모두 구할 수 있습니다.
이를 DP로 저장하여 같은 상태를 여러 번 계산하지 않도록 하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N, M;
int dp[1003][1003];
vector<pair<int,int>> inp;
int dist_diff(int a, int b){
return abs(inp[a].first - inp[b].first)
+ abs(inp[a].second - inp[b].second);
}
int solve(int a, int b){
if(a == M+1 || b == M+1)
return 0;
if(dp[a][b])
return dp[a][b];
int next = max(a,b)+1;
return dp[a][b] = min(
solve(a,next)+dist_diff(b,next),
solve(next,b)+dist_diff(a,next)
);
}
void print_police(){
int a = 0;
int b = 1;
for(int next=2; next<=M+1; next++){
if(dp[next][b] + dist_diff(a,next)
< dp[a][next] + dist_diff(b,next)){
cout << 1 << '\n';
a = next;
}
else{
cout << 2 << '\n';
b = next;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
inp.push_back({1,1});
inp.push_back({N,N});
for(int i=0;i<M;i++){
int y,x;
cin >> y >> x;
inp.push_back({y,x});
}
cout << solve(0,1) << '\n';
print_police();
return 0;
}풀이 흐름
- 경찰차의 시작 위치와 사건들을 하나의 배열에 저장합니다.
- 현재 두 경찰차가 마지막으로 처리한 사건 번호를 상태로 사용합니다.
- 다음 사건을 경찰차 1이 처리하는 경우와 경찰차 2가 처리하는 경우를 모두 계산합니다.
- 더 작은 이동 거리를 DP에 저장합니다.
- 저장된 DP 값을 이용하여 실제 어떤 경찰차가 사건을 처리했는지도 복원합니다.
구현 포인트
1. DP 상태 정의
DP는
dp[경찰차1 마지막 사건][경찰차2 마지막 사건]형태로 사용하였습니다.
즉,
dp[a][b]는
경찰차 1이 a번 사건, 경찰차 2가 b번 사건까지 처리한 상태에서 남은 사건들을 모두 처리하는 최소 이동 거리를 의미합니다.
2. 시작 위치도 사건처럼 저장
입력을 하나의 배열에서 처리하기 위해
inp[0] = (1,1)
inp[1] = (N,N)으로 저장하였습니다.
이후 실제 사건들은
inp[2]
~
inp[M+1]에 저장하였습니다.
이렇게 하면 모든 이동 거리를 동일한 함수로 계산할 수 있습니다.
3. 다음 사건 계산
현재 두 경찰차가
a
b까지 처리했다면
다음 처리해야 하는 사건은 항상
next = max(a,b)+1;입니다.
사건은 순서대로 처리해야 하기 때문에 가능한 다음 사건은 하나뿐입니다.
4. 두 가지 선택
현재 사건은
- 경찰차 1이 처리하거나
- 경찰차 2가 처리하거나
두 가지뿐입니다.
경찰차 1이 처리하는 경우
solve(next,b) + dist_diff(a,next)경찰차 2가 처리하는 경우
solve(a,next) + dist_diff(b,next)둘 중 작은 값을 현재 상태의 최소 비용으로 저장하였습니다.
return dp[a][b] = min(
solve(a,next)+dist_diff(b,next),
solve(next,b)+dist_diff(a,next)
);5. 메모이제이션
이미 계산한 상태라면 다시 계산하지 않습니다.
if(dp[a][b])
return dp[a][b];같은 상태에서는 이후 최소 이동 거리도 항상 동일하므로 DP를 사용할 수 있습니다.
6. 경로 복원
최소 거리뿐 아니라 어떤 경찰차가 사건을 처리했는지도 출력해야 합니다.
이를 위해 저장된 DP 값을 비교합니다.
if(dp[next][b] + dist_diff(a,next)
< dp[a][next] + dist_diff(b,next))경찰차 1을 선택한 경우가 더 작다면
cout << 1;아니면
cout << 2;를 출력하며 상태를 갱신합니다.
이 과정을 반복하면 최소 이동 거리를 만드는 사건 배정을 모두 복원할 수 있습니다.
