[백준 2159] 케익 배달 (C++)

2159번: 케익 배달

다익스트라

---

주문이 들어온 순서대로 배달한다는 게 문제의 핵심.

 

 

별이 시작점이다.

여러 최단거리 중 임의로 하나를 잡으면 위와 같은 경로가 생긴다.

처음에 다익스트라인 줄 모르고 3번 케이크에서 2, 1번 순으로 이동시키며 가장 짧은 거리만 찾아 그리디 하게 탐색할까 생각했었는데 이 문제와는 전혀 어울리지 않는 알고리즘이었다.

 

현재 위치한 지점의 고객번호와, 지금까지 이동한 거리, 현재 위치를 저장하고 있는 구조체를 만들어주었다.

그리고 일반적인 다익스트라의 dist 배열과는 다르게 하나의 정점마다 근처의 4개 지점까지 갈 수 있기 때문에 배열의 차원을 늘려서 4개의 지점에 대한 최단거리를 저장하도록 했다.

 

여기까지 사전 준비가 끝났다.

이제 다익스트라를 수행하며 마지막 손님을 만날 때까지 최단거리를 갱신, 탐색해준다.

-> 다음 정점을 찾는 과정이 현재 정점의 번호+1 인걸 빼면 일반적인 다익스트라와 매우 비슷하다!

 

손님을 번호 순대로 방문한다는 사실 덕분에 10만 개의 입력을 처리할 수 있었다.

만약 번호 순대로 방문한다고 명시되어있지 않았다면 N의 최대 개수가 1000개 정도로 줄어들지 않았을까?

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define LINF 1e15
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct POINT{
    pii coord; 
    ll d;
    int idx;
};
 
struct cmp{
    bool operator()(POINT &a, POINT &b){
        return a.d > b.d;
    }
};
 
int N;
pii rest[100001];
ll dist[100001][4];
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
void input(){
    cin >> N >> rest[0].first >> rest[0].second;
    for(int i = 1; i <= N; i++){
        cin >> rest[i].first >> rest[i].second;
    }
    for(int i = 0; i < 100001; i++){
        for(int k = 0; k < 4; k++){
            dist[i][k] = LINF;
        }
    }
}
 
int distance(pii &a, pii &b){
    return abs(a.first - b.first) + abs(a.second - b.second);
}
 
void Dijkstra(){
    priority_queue<POINT, vector<POINT>, cmp> pq;
    pq.push({rest[0], 0, 0});
    
    while(!pq.empty()){
        POINT now = pq.top();
        int next = now.idx+1;
        pq.pop();
        
        if(now.idx == N){
            cout << now.d << "\n";
            break;
        }
        
        for(int k = 0; k < 4; k++){
            pii np;
            np.first = rest[next].first + dr[k];
            np.second = rest[next].second + dc[k];
            ll next_dist = now.d + distance(now.coord, np);
            
            if(next_dist < dist[next][k]){
                pq.push({np, next_dist, next});
                dist[next][k] = next_dist;
            }
        }
    }
}
 
int main(){
    fastio
    input();
    Dijkstra();
    
    return 0;
}