[ 백준 16958 ] 텔레포트 (C++)

백준의 텔레포트(16958) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 이 문제를 플로이드 워셜(Floyd-Warshall)알고리즘을 통해서 구현해 보았다.

   플로이드 워셜 알고리즘에 대해서 간략하게 설명해보자면...

   하나의 맵에 존재하는 모든 정점간의 최단경로를 구하는데 주로 쓰이는 알고리즘이다.

   보통, 직접 연결할 때의 거리와, 특정 정점을 거쳐서 연결될 때의 거리를 비교해서 최단거리를 찾는 식으로 구현된다.

   구체적인 방법은 밑에서 코드를 통해서 확인해보자.

  

   먼저, 본인은 2차원 MAP을 하나 선언해주었는데, 이 MAP에서 저장되는 값들은 최소거리가 저장된다.

   MAP[a][b] = c 의 의미는 "a와 b의 거리는 c이다." 라는 것을 의미한다.

   우리는 저장할 때 특별한 경우만 주의해 주면 된다. 바로 두 도시 모두 특별한 도시일 때이다.

   특별한 도시일 때는 텔레포트를 이용해서 문제에서 주어진 T초 만에 갈 수 있다고 명시되어 있다.

   하지만 ! 무조건 텔레포트로 가야만 하는 것은 아니다.

   예를 들어서 특별한 도시 (1, 1)과 (2, 2)가 있다고 가정해보자. T = 3이다.

   그럼 이 둘의 거리는 3이 맞을까? 아니다. 텔레포트를 이용하지 않고 갈 경우, 2로 T보다 더 작은 시간만에 갈 수 있다.

   즉, 우리는 텔레포트를 사용할 수 있는 경우라고 하더라도, 이용하지 않는 경우와 비교를 해서

   더 작은 시간을 구해서 저장해 주어야 한다.

   일단, 초기적으로 이렇게 모든 거리를 구해서 MAP[][] 2차원배열에 저장해주자.

2) 하지만 우리가 구한 값들은 최소값이 아니다. 직접적인 거리일 뿐이다.

   우리가 구해야 할 값들은 최소값이다. 즉, A에서 B로 움직인다고 가정했을 때, A -> C -> B가 최소가 된다고 가정해보자.

   지금 우리가 저장해 놓은 값은, A -> B일때의 거리이지, 최소값이 아니라는 것이다. 이제 최소값을 찾기 위해서

   플로이드 워셜 알고리즘이 사용되게 된다.

   플로이드 워셜 알고리즘은 보편적으로 3중 for문을 이용해서 구현하게 된다. 다음과 같이

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 (MAP[i][j] > MAP[i][k] + MAP[k][j]) MAP[i][j] = MAP[i][k] + MAP[k][j];

    // 시작점 -> 도착점 보다, 시작점 -> 중간점 -> 도착점이 더 빠르다면 값을 갱신 !

        }
    }
}

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
int N, T, M;
int MAP[MAX][MAX];
vector<pair<pair<int, int>, int>> V;
vector<pair<int, int>> Cmd;
 
void Input()
{
    cin >> N >> T;
    for (int i = 0; i < N; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V.push_back(make_pair(make_pair(b, c), a));
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        a--; b--;
        Cmd.push_back(make_pair(a, b));
    }
}
 
int Dist(int x, int y, int xx, int yy) { return (abs(x - xx) + abs(y - yy)); }
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        int x = V[i].first.first;
        int y = V[i].first.second;
        int S = V[i].second;
 
        for (int j = 0; j < N; j++)
        {
            if (i == j) continue;
            int Distance;
            int xx = V[j].first.first;
            int yy = V[j].first.second;
            int SS = V[j].second;
 
            Distance = Dist(x, y, xx, yy);
            if (S == 1 && SS == 1)
            {
                if (Distance > T) Distance = T;
            }
            
            MAP[i][j] = Distance;
        }
    }
    
    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 (MAP[i][j] > MAP[i][k] + MAP[k][j]) MAP[i][j] = MAP[i][k] + MAP[k][j];
            }
        }
    }
 
    for (int i = 0; i < M; i++)
    {
        int Pos = Cmd[i].first;
        int Pos2 = Cmd[i].second;
 
        cout << MAP[Pos][Pos2] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}