백준 - 2159번 : 케익 배달 (C++)

풀이 방법 : DP

순서대로 케익 배달을 해야하는 문제로, 문제에서 고객의 위치에서 상하좌우로 인접한 곳까지만 가더라도 배달이 가능하다고 주어졌기 때문에 "고객 위치, 상, 하, 좌, 우" 5가지의 좌표를 고려해야한다.

격자 그림을 보고 반사적으로 그래프 탐색이 떠오를 수 있으나 장애물이 있거나 하는 이동 불가능한 좌표가 없고 단순히 맨해튼 거리의 합만 구하면 되므로 굳이 그럴 필요 없다.

무조건 주문이 들어온대로 순서대로 배달한다고 했으므로 i번째 고객한테 배달하는 루트는 i-1번째 고객에게 배달한 위치에서 출발하는 경우 뿐이다. 그렇기 때문에

i번째 항 = (i-1번째의 고객의 각 좌표들까지 도달하는 최단거리) + (i - 1번째의 각 좌표에서 i번째 고객의 각 좌표까지의 거리)

이런 식으로 점화식을 세워 마지막까지 누적시켜가면 된다.

또한 고객들의 좌표가 중복될 수 있다고 했으므로 양 끝을 계속 오가는 경우 거리의 총합이 2백억 가까이 갈 수 있으므로 거리의 총합을 저장하는 DP테이블은 int로는 표현이 불가능하므로 long long을 사용해주었다.

#include <iostream>
#include <cmath>

using namespace std;

const long long DistMax = 30000000001;
const int PosMax = 100000;

long long DP[100001][5] = {};
pair<int, int> Pos[100001] = {};

int DirX[5] = { 0, 0,0,1,-1 };
int DirY[5] = { 0, 1,-1,0,0 };

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    int StartX, StartY;
    cin >> StartX >> StartY;

    for (int i = 0; i < N; ++i)
    {
        cin >> Pos[i].first >> Pos[i].second;

        for (int j = 0; j < 5; ++j)
        {
            DP[i][j] = DistMax;
        }
    }

    for (int i = 0; i < 5; ++i)
    {
        int NextX = Pos[0].first + DirX[i];
        int NextY = Pos[0].second + DirY[i];

        if (NextX < 1 || NextX > PosMax || NextY < 1 || NextY > PosMax)
            continue;

        int Dist = abs(StartX - NextX) + abs(StartY - NextY);
        DP[0][i] = Dist;
    }

    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            int NextX = Pos[i].first + DirX[j];
            int NextY = Pos[i].second + DirY[j];

            if (NextX < 1 || NextX > PosMax || NextY < 1 || NextY > PosMax)
                continue;

            for (int k = 0; k < 5; ++k)
            {
                int CurX = Pos[i - 1].first + DirX[k];
                int CurY = Pos[i - 1].second + DirY[k];

                if (CurX < 1 || CurX > PosMax || CurY < 1 || CurY > PosMax)
                    continue;

                long long Dist = abs(CurX - NextX) + abs(CurY - NextY);
                DP[i][j] = min(DP[i][j], DP[i - 1][k] + Dist);
            }
        }
    }

    long long Min = DistMax;

    for (int i = 0; i < 5; ++i)
        Min = min(DP[N - 1][i], Min);

    cout << Min;
}