[C++] 2618번 경찰차 - DP

#include <iostream>
#include <algorithm>
#include <stack>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define MAX_W 1001
#define INF 987654321

using namespace std;

int N, W;  //도로의 개수 N, 사건의 개수 W
int inci[MAX_W][2];  //incident: 사건 (x좌표, y좌표)
int dp[MAX_W][MAX_W];  //Dynamic 
int Min, Minid;  //거리의 합

void input()
{
    cin >> N >> W;
    FOR(i, 1, W) cin >> inci[i][0] >> inci[i][1];
}

int range(int be, int af, int pol)  //before번째 좌표에서 after번째 좌표까지의 거리
{
    if(!be) {
        if(pol) return abs(inci[af][0]-N)+abs(inci[af][1]-N);
        else return abs(inci[af][0]-1)+abs(inci[af][1]-1);
    }
    
    return abs(inci[be][0]-inci[af][0])+abs(inci[be][1]-inci[af][1]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    FOR(i, 0, MAX_W-1) {
        FOR(j, 0, MAX_W-1) {
            if(i||j) dp[i][j]=INF;
        }
    }
    
    FOR(i, 1, W) {  //마지막으로 경찰차가 움직인 위치를 기준으로 dp
        FOR(j, 0, i-1) {
            dp[i][j] = min(dp[i][j], dp[i-1][j]+range(i-1, i, 0));
            dp[i][i-1] = min(dp[i][i-1], dp[j][i-1]+range(j, i, 0));
            dp[i-1][i] = min(dp[i-1][i], dp[i-1][j]+range(j, i, 1));
            dp[j][i] = min(dp[j][i], dp[j][i-1]+range(i-1, i, 1));
        }
    }
    
    Min=INF; int Minidx, Minidy;
    FOR(i, 0, W-1) {
        if(Min > dp[i][W]) {
            Min=dp[i][W], Minidx=i, Minidy=W;
        }
        if(Min > dp[W][i]) {
            Min=dp[W][i], Minidx=W, Minidy=i;
        }
    }
    cout << Min << '\n';
    
    stack<int> s; int idx, idy;
    for(int i=W; i>=1; i--) {  //역 탐색
        int x=INF, tmp;
        
        if(i!=1) {
            if(Minidx==i && Minidy!=i-1) {
                tmp=1; Minidx--;
            }
            else if(Minidx!=i-1 && Minidy==i) {
                tmp=2; Minidy--;
            }
            else {
                for(int j=0; j<i-1; j++) {
                    if(Minidx==i-1 && Minidy==i && x > dp[i-1][j]+range(j, i, 1)) {
                        x = dp[i-1][j]+range(j, i, 1); tmp=2; idx = i-1, idy = j;
                    }
                    if(Minidx==i && Minidy==i-1 && x > dp[j][i-1]+range(j, i, 0)) {
                        x = dp[j][i-1]+range(j, i, 0); tmp=1; idx = j, idy = i-1;
                    }
                }
                Minidx = idx, Minidy = idy;
            }
            s.push(tmp);
        }
        else {
            if(Minidx) s.push(1);
            else s.push(2);
        }
    }
    
    while(!s.empty()) {
        cout << s.top() << '\n';
        s.pop();
    }
    
    return 0;
}

구현 아이디어는 빨리 냈으나, 역추적 과정에서 상당히 애먹었다. 구현 아이디어 20~30분, 역추적 2시간 30분

 

ㅁ;니ㅏ을;ㅁ니ㅏ을;ㅁ니ㅏㅡㅇㄹ;미나음;ㄴ이ㅏㅡㅁ;ㄴ이ㅡ;ㅂ지ㅏ드;ㅈ비ㅏㄷ스

 

아무리 봐도 이건 플래 5는 아닌 듯한데....

 

<알고리즘>

1. 최종 경찰차들의 위치가 같으면 다음 사건이 일어나도 똑같이 움직이므로 이들을 통일시키면 DP를 구현할 수 있다.
2. 역추적을 하는 과정에서 확인해야 할 점이 실제로 역추적한 곳에서 경찰차가 다음 곳으로 움직일 수 있는가? 거리가 다른 점과 비교해서 최소인가? 를 확인해주어야 한다.

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.