백준 12908번. 텔레포트 3(c++) / 구현

시작점을 제외하고 거칠 수 있는 점이 총 7개(텔레포트 6개 + 도착 점 1개)이다.

총 7개의 점을 순열로 순서를 정하고

 

순서에 맞게 각 점사이의 거리를 더하고 텔레포트를 하기 위한 시간 10을 더한다.

텔레포트를 하기 위한 시간을 왜 더했는지 묻는다면....

V.push_back({a, b, c, d}) 와 같이 구조체 형태로 텔레포트지점을 저장했기 때문이다.

그리고 중간에 도착지점에 도착한다면 break로 빠져나왔다.

 

흠..이 문제는 설명하기가 참 어렵다...ㅎㅎ

그냥 코드를 읽으면 이해하기 더 쉽다.

 

코드 첨부

// 텔레포트 3
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
 
int start_x, start_y, end_x, end_y, a, b, c, d;
struct subin { int x1, y1, x2, y2;};
vector<subin> V;
vector<int> seq; // 방문할 순서(idx)
long long final = INT_MAX;
 
long long cal(int x, int y, int z, int w)
{
    return abs(z-x) + abs(w-y);
}
 
int main()
{
    cin>>start_x>>start_y;
    cin>>end_x>>end_y;
 
    for(int i=0; i<3; i++){
        cin>>a>>b>>c>>d;
 
        V.push_back({a, b, c, d});
        V.push_back({c, d, a, b});
    }
    V.push_back({end_x, end_y, end_x, end_y});
 
    for(int i=0; i<7; i++){
        seq.push_back(i);
    }
 
    do{
        long long dist = 0;
        int nx = start_x;
        int ny = start_y;
        for(int i=0; i<seq.size(); i++){
            dist += cal(nx, ny, V[seq[i]].x1, V[seq[i]].y1); // 전의 좌표에서 지금 좌표까지의 거리
            if(V[seq[i]].x2==end_x && V[seq[i]].y2==end_y){ // 도착
                break;
            }
            dist += 10; // 텔레포트해서 (x1, y1) -> (x2, y2)로 이동했다.
            // (nx, ny)값 갱신
            nx = V[seq[i]].x2;
            ny = V[seq[i]].y2;
        }
        final = min(final, dist);  
 
    }while(next_permutation(seq.begin(), seq.end()));
 
    cout<<final<<"\n";
    return 0;
}

 

 

문제 첨부

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

12908번: 텔레포트 3

 

github 첨부

https://github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/12908.cpp

jungahshin/algorithm