16958번 텔레포트

https://www.acmicpc.net/problem/16958

다익스트라 : https://hsdevelopment.tistory.com/389

# jh05013 # 복습 # 구현 # 생각 # 필수 # 아이디어 # 맨하탄 # 맨하튼 # 거리

복습 필수 다익스트라 플로이드 코테 코딩 추천 

bfs로 풀려다가, visit 방문 처리가 복잡할 것 같아서 다익스트라로 풀었다.

vector p하고 우선순위 큐인 pq의 first, next 구분을 잘 하자.

또한, 무작정 텔레포트 시간을 넣는 것이 아니라 실질적인 거리와의 비교를 통해 더 작은 것을 넣어야 한다.

그런데, 다익스트라로 푸니 시간이 무려 1132ms나 걸렸다.

플로이드 와샬도 868ms나 걸렸다.

하지만 채점 현황을 보니 0ms 코드도 있었다.

더 짧게 하려면 어떻게 해야할까 고민하던 중에 jh05013님의 블로그 힌트(?)를 참고하였다.

https://blog.naver.com/jh05013/221470412597

알고보니 |r1-r2| + |c1-c2|는 맨하탄 거리라는 식이고, 요약하자면,

어떤 정점 a(r1, c1)에서 다른 정점 b(r2, c2)로 곧바로 가는 것(|r1-r2| + |c1-c2|)이

여러 정점들을 거쳐가는 것보다 더 짧거나 같다는 것이다.

또한, 이 문제에서는 텔레포트를 2번 이상 쓸 이유가 없다.

텔레포트는 T로 고정되어 있는 값이고, 2번 이상 쓴다면, 추가적인 거리를 또 더해야 하기 때문에 최솟값을 구하지 못 한다.

요약하자면, 

1. 곧바로 가는 경우(내 코드의 d1)

도시(f) →  도시(t) = |r1-r2| + |c1-c2|

2. 시작(f)에서 가장 가까운 특별한 도시(s1)와 도착(t)에서 가장 가까운 특별한 도시(s2)를 이용해서 가는 경우(내 코드의 d2)

f와 s1의 맨하탄 거리를 구하고

T를 더한다.(s1에서 s2로 텔레포트)

그리고, s2와 t의 맨하탄 거리도 더한다.

따라서, 답은 min(d1, d2)이다.

추가적으로 시작(f)과 도착(t)이 특별한 도시일 경우를 대비해

맨 아래 쪽의 코드에서 31번 째 줄을 추가해야 한다.

시작(f)과 도착(t)이 특별한 도시일 경우 어차피 d2를 구하는 과정에서 0으로 되는 부분이 나온다.

이유는 자기 자신에 대한 좌표를 계산하기 때문이다.

다익스트라 1132ms

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1002
#define INF 2000000000
 
typedef struct info
{
    int s, x, y;
}info;
 
int n, T, m, dist[Max];
vector<info> v;
vector<pair<int, int> > p[Max];
 
int dijstra(int f, int t)
{
    fill(dist, dist + Max, INF);
    priority_queue<pair<int, int> > pq;
 
    dist[f] = 0;
    pq.push({ 0, f });
    // pq 우선순위 큐
    // first : 거리
    // second : 정점
 
    while (!pq.empty())
    {
        int now = pq.top().second;
        int now_cost = -pq.top().first;
 
        pq.pop();
 
        if (dist[now] < now_cost) {
            continue;
        }
 
        // p 벡터
        // next.first : 정점
        // next.second : 거리
        for (auto next : p[now]) {
            if (dist[next.first] > dist[now] + next.second) {
                dist[next.first] = dist[now] + next.second;
                pq.push({ -dist[next.first], next.first });
            }
        }
    }
 
    return dist[t];
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &n, &T);
    int s, x, y;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &s, &x, &y);
        v.push_back({ s, x, y });
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (v[i].s == 1 && v[j].s == 1) {
                // 실질적인 거리와 텔레포트 시간 중 더 작은 값을 부여해야 한다.
                // 무조건 텔레포트 시간을 넣어서는 안 된다.
                int distance = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
                distance = min(distance, T);
                p[i].push_back({ j, distance });
                p[j].push_back({ i, distance });
            }
            else {
                int distance = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
                p[i].push_back({ j, distance });
                p[j].push_back({ i, distance });
            }
        }
    }
 
    scanf("%d", &m);
    int f, t;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &f, &t);
        printf("%d\n", dijstra(f - 1, t - 1));
    }
 
    return 0;
}

플로이드 와샬 868ms

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1002
#define INF 2000000000
 
typedef struct info
{
    int s, x, y;
}info;
 
int n, T, m, p[Max][Max];
vector<info> v;
 
void fw()
{
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
 
                if (p[i][j] > p[i][k] + p[k][j]) {
                    p[i][j] = p[i][k] + p[k][j];
                }
            }
        }
    }
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &n, &T);
    int s, x, y;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &s, &x, &y);
        v.push_back({ s, x, y });
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            p[i][j] = p[j][i] = i == j ? 0 : INF;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (v[i].s == 1 && v[j].s == 1) {
                // 실질적인 거리와 텔레포트 시간 중 더 작은 값을 부여해야 한다.
                // 무조건 텔레포트 시간을 넣어서는 안 된다.
                int distance = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
                distance = min(distance, T);
                p[i][j] = p[j][i] = distance;
            }
            else {
                int distance = abs(v[i].x - v[j].x) + abs(v[i].y - v[j].y);
                p[i][j] = p[j][i] = distance;
            }
        }
    }
 
    fw();
 
    scanf("%d", &m);
    int f, t;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &f, &t);
        printf("%d\n", p[f - 1][t - 1]);
    }
 
    return 0;
}

아이디어(?)가 적용된 코드 0ms

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1002
#define INF 2000000000
 
typedef struct info
{
    int number, x, y;
}info;
 
int n, T, m;
vector<info> General, Special;
info p[Max];
int Dist[Max][Max], near[Max];
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d", &n, &T);
    int s, x, y;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &s, &x, &y);
        if (s) { 
            // 특별한 도시
            Special.push_back({ i, x, y });
 
            // 자신이 특별한 도시라면, 가장 가까운 특별한 도시는 자신이다. 
            near[i] = i;
        }
        else { 
            // 일반 도시
            General.push_back({ i, x, y });
        }
 
        // 모든 도시의 위치를 저장(x, y)
        p[i] = { s, x, y };
    }
 
    int General_size = General.size();
    int Special_size = Special.size();
 
    // 일반 도시에서 가장 가까운 특별한 도시를 찾는다
    for (int i = 0; i < General_size; i++) {
        int Min = 2e9, pn;
        for (int j = 0; j < Special_size; j++) {
            if (Min > abs(General[i].x - Special[j].x) + abs(General[i].y - Special[j].y)) {
                Min = abs(General[i].x - Special[j].x) + abs(General[i].y - Special[j].y);
                pn = Special[j].number;
            }
        }
        // 일반 도시에서 가장 가까운 특별한 도시의 번호를 저장
        near[General[i].number] = pn;
    }
 
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int f, t;
        scanf("%d %d", &f, &t);
 
        --f; --t; // 조심
 
        // 직접 이동할 때
        int d1 = abs(p[f].x - p[t].x) + abs(p[f].y - p[t].y);
        
        // 특별한 도시를 거쳐갈 때
        int d2 = 
              abs(p[f].x - p[near[f]].x) + abs(p[f].y - p[near[f]].y) 
            + T
            + abs(p[t].x - p[near[t]].x) + abs(p[t].y - p[near[t]].y);
 
        printf("%d\n", min(d1, d2));
    }
 
    return 0;
}