BOJ 12908

17 Mar 2020 • ProblemSolving

텔레포트 3

문제출처

문제 해석

  • 수빈이의 위치(sx,sy)에서 집(ex,ey)로 이동하기 위한 최소 시간을 구하는 문제입니다.
  • 이동하는 방법은 아래와 같습니다.
    1. 첫번째로, 점프를 하는 것입니다. 상하좌우로 한칸씩 이동합니다.(1초)
    2. 두번째로, 텔레포트를 사용합니다. 텔레포트할 수 있는 방법은 3가지가 있으며, (x1,y1),(x2,y2)로 서로 이동이 가능합니다.(10초)

설계(20)

  • 먼저 각 좌표의 범위가 <=10^9이므로 1칸씩 이동하게 구현하면 시간초과가 날 것입니다.
  • 시간초과를 방지하기 위해서는 Haming Distance를 이용해야 합니다.
  • 양방향 텔레포트가 3가지 있기 때문에 단방향으로 6가지 텔레포트가 있습니다.
  • 시작좌표로부터 해당 6가지와 도착 좌표 이동순서를 정하고, 최소 dist를 갱신합니다.(O(7!))
  • 만약, 이동순서대로 이동을 하는 도중에 도착지에 먼저 도착하면 break를 이용하여 알맞은 시간을 구해주게 됩니다.

구현(40)

코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
struct P{
    ll x1,y1,x2,y2;
    P(ll X1, ll Y1, ll X2 ,ll Y2) : x1(X1),y1(Y1),x2(X2),y2(Y2) {}
};
ll Dist(ll x1, ll y1, ll x2 , ll y2){
    return abs(x1-x2)+abs(y1-y2);
}
vector<P> adj;
vector<int> v;
vector<int> used;
int sx,sy,ex,ey;
ll ans = 1e15;
void go(int idx){
    if (idx == 7){
        int nx = sx;
        int ny = sy;
        ll cur_d = 0;
        for (int i=0;i < v.size(); i++){
            cur_d += Dist(nx,ny,adj[v[i]].x1,adj[v[i]].y1);
            if (adj[v[i]].x2 == ex && adj[v[i]].y2 == ey) break;
            cur_d += 10;
            nx = adj[v[i]].x2;
            ny = adj[v[i]].y2;
        }
        if (ans > cur_d) ans = cur_d;
        return;
    }
    for (int i = 0; i < 7; i++){
        if (used[i]) continue;
        used[i] = 1;
        v.push_back(i);
        go(idx+1);
        used[i] = 0;
        v.pop_back();
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    used = vector<int>(7);
    cin >> sx >> sy >> ex >> ey;
    for (int i = 0; i < 3; i++){
        ll x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        adj.push_back(P(x1,y1,x2,y2));
        adj.push_back(P(x2,y2,x1,y1));
    }
    adj.push_back(P(ex,ey,ex,ey));
    go(0);
    cout << ans <<"\n";
    return 0;
}
디버깅
  • 처음에, Greedy하게 시작좌표로부터 최소 Haming Distance를 갱신시켜주면서 도착지가 나올 때 까지 반복하게 구현했지만 WA가 나왔습니다.
  • 1->2로 갈때 dist가 최소가 아니어도 다음 2->도착지의 dist의 합이 더 최소인 경우가 생기기 때문입니다.
제출결과
  • 0ms

마무리

  • 완전탐색으로 구현이 가능한 문제였습니다. greedy문제로 접근을 해서 WA가 나왔습니다. 시간복잡도가 적은것을 알고도 완전탐색을 사용하지 않은게 실수였습니다.
 BOJ

Related Posts