[백준] 12908번 : 텔레포트 (C++)

12908번 : 텔레포트 3

---

문제)

수빈이는 크기가 무한대인 격자판 위에 살고 있다. 격자판의 각 점은 두 정수의 쌍 (x, y)로 나타낼 수 있다.

제일 처음에 수빈이의 위치는 (xs, ys)이고, 집이 위치한 (xe, ye)로 이동하려고 한다.

수빈이는 두 가지 방법으로 이동할 수 있다. 첫 번째 방법은 점프를 하는 것이다. 예를 들어 (x, y)에 있는 경우에 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 이동할 수 있다. 점프는 1초가 걸린다.

두 번째 방법은 텔레포트를 사용하는 것이다. 텔레포트를 할 수 있는 방법은 총 세 가지가 있으며, 미리 정해져 있다. 텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다는 것이다. 텔레포트는 10초가 걸린다.

수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000)

셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000)

입력으로 주어지는 모든 좌표 8개는 서로 다르다.

 

 

 

출력 :

수빈이가 집에 가는 가장 빠른 시간을 출력한다.

 

 

 

 

풀이)

 

// 12908. 텔레포트 3
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
 
using namespace std;
 
 
int n, m;
int x, y;
 
vector<pair<long long, int>> vec;
vector<long long> dist;
 
long long cal(int a, int b)
{
    return (long long) abs(vec[a].first - vec[b].first) 
            + (long long) abs(vec[a].second - vec[b].second);
}
 
void dijkstra()
{
    priority_queue<pair<long long, int>
            , vector<pair<long long, int>>
            , greater<pair<long long, int>>> pq;
    dist[0] = 0;
    pq.push(make_pair(0, 0));
 
    while (!pq.empty())
    {
        int cur = pq.top().second;
        long long d = pq.top().first;
        pq.pop();
 
        if (dist[cur] < d) continue;
 
        for (int i = 0; i < 8; i++)
        {
            long long nd = d + cal(cur, i);
            int nxt = i;
 
            if ((cur == 2 && i == 3)
                || (cur == 3 && i == 2)
                || (cur == 4 && i == 5)
                || (cur == 5 && i == 4)
                || (cur == 6 && i == 7)
                || (cur == 7 && i == 6))
            {
                nd = d + 10;
            }
            
            if (dist[nxt] > nd)
            {
                dist[nxt] = nd;
                pq.push(make_pair(nd, nxt));
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
 
    cin >> n >> m;
    dist.resize(8, LONG_MAX);
    vec.push_back(make_pair(n, m));
    
    cin >> x >> y;
    vec.push_back(make_pair(x, y));
 
    int a, b;
    for (int i = 0; i < 6; i++)
    {
        cin >> a >> b;
        vec.push_back(make_pair(a, b));
    }
 
    dijkstra();
 
    cout << dist[1];
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/12908 

12908번: 텔레포트 3