BOJ2618 경찰차

BOJ2618 경찰차

 

 

dp[ i ][ j ]

dist = 마지막으로 A, B가 각각 i, j를 처리했을 때 움직인 총 거리

T = 가장 최근 사건을 처리하기 직전의 상태

 

 

STEP 1.  w=1일 때 dp[ 1 ][ 0 ], dp[ 0 ][ 1 ] 갱신한다.

 

STEP 2.  w=2~W일 때 dp[ * ][ w ]와 dp[ w ][ * ]를 구한다.

w-1번째, w번째 사건을 처리하는 경찰차가 각각 무엇인지에 따라 구해주면 된다.

A-A: [ w-1 ][ * ] → [ w ][ * ]

A-B: [ w-1 ][ * ] → [ w-1 ][ w ]

B-A: [ * ][ w-1 ] → [ w ][ w-1 ]

B-B: [ * ][ w-1 ] → [ * ][ w ]

 

ㆍ*에 들어갈 수는 0부터 w-2까지여야 한다.

ㆍdist 계산할 때 인덱스를 이용해 acc배열을 참조한다.

    다만 0인 경우 A는 { 1, 1 }, B는 { N, N }으로 해줄 것

ㆍ트래킹을 위해 T도 갱신해줘야 한다.

 

STEP 3.  정답이 되는 최소 거리를 고른다.

dp[ 0 ][ W ] ~ dp[ W-1 ][ W ], dp[ W ][ 0 ] ~ dp[ W ][ W-1 ] 중에 가장 최소 거리인 것을 고른다.

이때부터 A는 트래킹을 위해 이용한다.

 

STEP 4.  T를 이용해 트래킹해준다.

 

 

코드

#include <cstdio>
#include <cmath>
#include <stack>
#include <utility>
using namespace std;
#define INF 987654321
#define ff first
#define ss second
typedef pair<int, int> pii;

struct info {
    int dist = INF;
    pii T;
};
info dp[1001][1001];
pii acc[1001];
//dp[i][j]: A가 마지막으로 i를 처리, B가 마지막으로 j를 처리한 상태
//acc[w]: w-th Accident

int main() {
    int N, W, x, y, tmp;
    scanf("%d%d", &N, &W);

    // STEP 1. First Accident
    scanf("%d%d", &x, &y); acc[1] = { x,y };
    dp[1][0].dist = x - 1 + y - 1, dp[0][1].dist = N - x + N - y, dp[1][0].T = dp[0][1].T = { 0,0 };
    
    // STEP 2. 2~W-th Accident
    pii A, B;
    for (int w = 2; w <= W; ++w) {
        scanf("%d%d", &x, &y); acc[w] = { x,y };
        for (int k = 0; k < w - 1; ++k) {
            A = acc[w - 1];                     //AA [w-1][k]->[w][k]
            dp[w][k].dist = dp[w - 1][k].dist + abs(x - A.ff) + abs(y - A.ss);
            dp[w][k].T = { w - 1,k };

            B = (k) ? acc[k] : make_pair(N, N); //AB [w-1][k]->[w-1][w]
            tmp = dp[w - 1][k].dist + abs(x - B.ff) + abs(y - B.ss);
            if (dp[w - 1][w].dist > tmp) dp[w - 1][w].dist = tmp, dp[w - 1][w].T = { w - 1, k };

            B = acc[w - 1];                     //BB [k][w-1]->[k][w]
            dp[k][w].dist = dp[k][w - 1].dist + abs(x - B.ff) + abs(y - B.ss);
            dp[k][w].T = { k, w - 1 };

            A = (k) ? acc[k] : make_pair(1, 1); //BA [k][w-1]->[w][w-1]
            tmp = dp[k][w - 1].dist + abs(x - A.ff) + abs(y - A.ss);
            if (dp[w][w - 1].dist > tmp) dp[w][w - 1].dist = tmp, dp[w][w - 1].T = { k, w - 1 };
        }
    }
    
    // STEP 3. Get Minimum Distance
    int ANS = 987654321;
    for (int k = 0; k < W; ++k) {
        if (ANS > dp[W][k].dist) ANS = dp[W][k].dist, A = { W,k };
        if (ANS > dp[k][W].dist) ANS = dp[k][W].dist, A = { k,W };
    }
    printf("%d\n", ANS);

    // STEP 4. Tracking
    stack<int> S;
    while (W) {
        S.push((A.first == W) ? 1 : 2);

        A = dp[A.first][A.second].T; W--;
    }
    while (!S.empty()) printf("%d\n", S.top()), S.pop();
    
    return 0;
}

 

 

 

1. 아주 여러 번 틀리고 완전히 다른 방법으로 접근해서 맞았다. 이것도 최선을 다한다는 문제와 비슷하게 어디까지 고려할 지 감을 못 잡은 게 이전에 못 푼 원인. 최선을 다하는 문제는 그리디적으로 생각하면 완벽히 풀 수 없는 것 같다.

2. 게임이론 태그는 없지만 내가 느끼기엔 비슷한 구석이 있는 것 같다,, 아마 내가 푼 방식 때문인 것 같은데

3. 분명 더 간단히 푸는 방법이 있다. 지금은 뭔가 하드코딩한 기분이 든다