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

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

 

 

3개의 텔레포트 구간이 존재하고 시작점 x좌표 y좌표 도착점 x좌표 y좌표가 존재할때

시작점에서 도착점으로 갈때 가장 최소의 시간을 출력하는 문제이다.

 

이때 텔레포트 구간은 시작점과 도착점이 존재한다 양방향이기 때문에

시작점에서 도착점으로 이동할 수 있고

도착점에서 시작점으로 이동할 수 있다. 이때 텔레포트를 사용하면 10초의 시간이 소모된다.

 

즉 이 문제는 6개의 텔레포트 구간이 존재하고 텔레포트를 안타는 경우도 있기 때문에

 

총 경우의 수는 $$O(3^7)$$ 이 된다.

 

완전탐색해도 시간이 충분하기 때문에 완전탐색으로 구현하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

struct Tree {
    int Node, left, right;
};

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
ll xs, ys, xe, ye;
vector<tuple<ll, ll, ll, ll>> v(3);
ll answer = INF;

bool check(vector<int> &arr) {
    for(auto &it : arr) {
        if(it != 5) {
            it++;
            return true;
        }
        else {
            it = -1;
        }
    }

    return false;
}

void solve() {
    vector<int> seq(3, -1);

    answer = abs(xe - xs) + abs(ye - ys);

    do {
        ll startx = xs;
        ll starty = ys;
        ll tmp = 0;

        for(auto &it : seq) {
            if(it == -1) continue;

            tmp += abs(startx - get<0>(v[it])) + abs(starty - get<1>(v[it])) + 10;
            startx = get<2>(v[it]);
            starty = get<3>(v[it]);
        }

        tmp += abs(xe - startx) + abs(ye - starty);
        answer = min(answer, tmp);
    } while(check(seq));

    cout << answer;
}

void input() {
    cin >> xs >> ys >> xe >> ye;

    for(int i = 0; i < 3; i++) {
        auto &a = v[i];

        cin >> get<0>(a) >> get<1>(a) >> get<2>(a) >> get<3>(a);
        v.push_back({get<2>(a), get<3>(a), get<0>(a), get<1>(a)});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

로직을 하나씩 살펴보면

 

v 벡터에는 시작점과 도착점이 기록된 텔레포트가 존재한다. 이때 6개의 텔레포트 구간이 있기 때문에

입력받으며 도착점과 시작점의 반대인 구간을 넣어주었다.

 

이후 seq 리스트는 텔레포트를 3번타는데에 상태 변수를 나타낸다. 이 변수는 -1부터 5까지 변할 수 있으며

-1이 의미하는건 선택하지 않은 것이고 0부터 5는 몇번째 텔레포트를 이용하는것을 의미한다.

 

따라서 완전탐색해서 가장 낮은 거리를 출력한다.