백준 2618 경찰차

좀 어려워 보이는 문제를 잡아봤다. 두 경찰차가 있고, 하나는 1,1에서 나머지 하나는 N,N에서 출발한다. 경찰차가 격자무늬 도시를 돌아다니며 사건들을 해결하는데, 그 과정에서 이동하는 최소값과 경로를 출력하는 문제이다.

 

처음에 그냥 답이라도 나왔으면 좋겠다 하고 각 사건마다 가장 가까운 경찰차를 이동하면서 문제를 풀었는데, 틀렸다. 당연히 그런게, 만약 두 경찰차가 모두 같은 거리에 떨어져 있으면 이 경우는 어떻게 할지 정의되지 않아 최적해 탐색은 물 건너간다...

머리 쥐어뜯다가 질문 게시판을 탐색해보고 DP 배열 감을 잡았다.

dp[i][j] = 경찰차 1이 가장 마지막으로 i번째 사건을 했고, 경찰차 2가 가장 마지막으로 j번째 사건을 했을 때 이동 최소 거리로 정의를 하자.

이렇게 dp를 구성하면, 각 경찰차의 위치는 사건의 위치를 사용해 구할 수 있다.

우리는 이제 사건을 하나씩 하나씩 보면서 이걸 경찰차 1이 했을 때, 경찰차 2가 했을때로 분기하면서 dp를 채울 수 있다.

그렇다, TSP와 유사하게 DFS를 사용해 사건 수 깊이의 탐색이 이루어진다.

그렇게 탐색을 통해 최소 비용을 구할 수 있다.

 

그렇다면 경로는 어떻게 해야할까?

여기서 막혀서 더 찾아보니 그냥 거의 비슷하게 탐색하는 방법이 많이 사용되더라. 다만 이때는 두개를 모두 분기할 필요 없이, 이미 DP 배열이 채워 있으므로 각각 값을 찾아서 하나씩 출력이 이루어진다.

---

#include <iostream>
#include <vector>
#include <cstring>

int g_A_n;
int g_n;
#define MAX 1001
int dp[MAX][MAX];
std::pair<int, int> AList[MAX];

int get_dist(std::pair<int, int> police_car, std::pair<int,int> accident)
{
    return (std::abs(police_car.first - accident.first) + std::abs(police_car.second - accident.second));
}

// int dist_dfs(int P1, int P2, std::vector<std::vector<int>> &dp, std::vector<std::pair<int, int> > AList)
int dist_dfs(int P1, int P2)
{
    if (P1 == g_A_n || P2 == g_A_n) // 마지막 사건까지 했을 경우
        return 0;
    if (dp[P1][P2] != -1) return dp[P1][P2]; // dp 배열에 값이 이미 있을 경우

    int nextAcc = std::max(P1, P2) + 1; // 다음 사건 번호
    int P1Dist, P2Dist;

    // 다음 사건을 P1이 할 경우 거리 계산
    if (P1 == 0) 
        P1Dist = get_dist(std::make_pair(1,1), AList[nextAcc]);
    else
        P1Dist = get_dist(AList[P1], AList[nextAcc]);

    // 다음 사건을 P2가 할 경우 거리 계산
    if (P2 == 0)
        P2Dist = get_dist(std::make_pair(g_n,g_n), AList[nextAcc]);
    else
        P2Dist = get_dist(AList[P2], AList[nextAcc]);

    //각각의 경우 dfs로 탐색
    // int P1Result = P1Dist + dist_dfs(nextAcc, P2, dp, AList);
    // int P2Result = P2Dist + dist_dfs(P1, nextAcc, dp, AList);

    int P1Result = P1Dist + dist_dfs(nextAcc, P2);
    int P2Result = P2Dist + dist_dfs(P1, nextAcc);

    //두 값 중 낮은 값을 dp에 저장.
    dp[P1][P2] = std::min(P1Result, P2Result);
    return dp[P1][P2];
}

// void print_route_dfs(int P1, int P2, std::vector<std::vector<int>> dp, std::vector<std::pair<int, int> > AList)
void print_route_dfs(int P1, int P2)
{
    if (P1 == g_A_n || P2 == g_A_n) // 마지막 사건까지 했을 경우
        return ;

    int nextAcc = std::max(P1, P2) + 1; // 다음 사건 번호
    int P1Dist, P2Dist;

    // 다음 사건을 P1이 할 경우 거리 계산
    if (P1 == 0) 
        P1Dist = get_dist(std::make_pair(1,1), AList[nextAcc]);
    else
        P1Dist = get_dist(AList[P1], AList[nextAcc]);

    // 다음 사건을 P2가 할 경우 거리 계산
    if (P2 == 0)
        P2Dist = get_dist(std::make_pair(g_n,g_n), AList[nextAcc]);
    else
        P2Dist = get_dist(AList[P2], AList[nextAcc]);

    //각각의 경우 dfs로 탐색
    if (dp[nextAcc][P2] + P1Dist < dp[P1][nextAcc] + P2Dist)
    {
        std::cout << 1 << '\n';
        // print_route_dfs(nextAcc, P2, dp, AList);
        print_route_dfs(nextAcc, P2);
    }
    else
    {
        std::cout << 2 << '\n';
        // print_route_dfs(P1, nextAcc, dp, AList);
        print_route_dfs(P1, nextAcc);
    }
}


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    int A_n;
    // std::vector<std::pair<int, int> > AList;
    std::cin >> n >> A_n;
    g_A_n = A_n;
    g_n = n;
    // AList.push_back(std::make_pair(-1, -1));
    for (int i = 1; i <= A_n; i++)
    {
        int x, y;
        std::cin >> x >> y;
        AList[i].first = x;
        AList[i].second = y;
        // AList.push_back(std::make_pair(x, y));
    }

    // std::vector<std::vector<int>> dp(g_A_n + 1, std::vector<int>(g_A_n + 1, -1));
    memset(dp, -1, sizeof(dp));

    // int dist = dist_dfs(0, 0, dp, AList);
    int dist = dist_dfs(0, 0);
    std::cout << dist << '\n';
    // print_route_dfs(0, 0, dp, AList);
    print_route_dfs(0, 0);
    // std::pair<int, int> P1(0,0);
    // std::pair<int, int> P2(n - 1, n - 1);
    // std::vector<int> solveList;
    // int dist = 0;
    // 매 사건마다 가장 가까운 경찰차가 가는걸로 구현해보자. -> 9% 틀렸습니다.
    // for (auto accident : AList)
    // {
    //     int P1Dist = get_dist(P1, accident);
    //     int P2Dist = get_dist(P2, accident);
    //     if (P1Dist > P2Dist)
    //     {
    //         dist += P2Dist;
    //         solveList.push_back(2);
    //         P2 = accident;
    //     }
    //     else
    //     {
    //         dist += P1Dist;
    //         solveList.push_back(1);
    //         P1 = accident;
    //     }
    // }
    // std::cout << dist << '\n';
    // for (int p : solveList)
    //     std::cout << p << '\n';
}

// 왜 벡터를 주면 타임아웃이 뜨고 전역배열로 하면 잘 되는거지? 무슨 의미인것이지?

 

주석처리 된것을 보면 알 수 있겠지만, 삽질을 많이 했다. 그리고 왜 안되는건지 더 찾아봐야겠지만, 왜 벡터로 값을 넘겨줬을때는 틀렸습니다가 뜨는지 모르겠다. 벡터로 했을 때 값 샘플 테스트케이스 답 나오는건 확인했는데 왜 계속 틀렸다고... 뜨는지...

전역 배열로 할당해서 접근하니 답이 나온다.. 에휴...

뭔가 DP문제들도 틀이 있는건가?? 싶긴 한데 아직 잘 모르겠다... 더 풀어봐야지!

 

오늘도 평온한 하루가 되길. 슨민.