[ SWEA 1247 ] 최적경로 (C++)

SWExpertAcademy의 최적경로(1247 / D5) 문제이다.

[ 문제풀이 ]

1) 회사에서 출발해서 모든 고객들의 집을 방문 후 자신의 집으로 돌아갈 때 가장 짧은 경로를 찾아야 하는 문제이다.

   본인이 가장 첫 번째로 생각한 것은 '순열 구현' 이다.

   고객들의 집을 방문하는 순서를 '순열'로 구현해 보는 것이다. 조합이 아닌 순열인 이유는 순서에 따라서 결과가 달라질 수

   있기 때문이다. 예를 들어서 A, B, C 이렇게 3명의 고객의 집이 있다고 했을 때,

   회사 - A - B - C - 집 / 회사 - B - A - C - 집 / 회사 - C - A - B - 집 / 은 모두 결과가 다를 것이기 때문이다.

   즉, 순서에 영향을 미치는 수열이기 때문에 조합이 아닌 순열로써 구현해 주었다.

   [ 순열 구현하기 바로가기(Click) ]

  순열을 구했으면 그 구해준 순열대로 거리만 계산해서 최솟값을 찾아주면 된다. 이러면 실행시간이 조금 오래걸리지만

  그래도 pass를 받을 수는 있다.

  하지만, 조금 오래 걸리는 것 같아서 본인이 시간을 줄인 방법에 대해서 이야기해 보겠다.

  순열을 구할 때, 단순히 순열을 고르는 내용만 구하는 것이 아니라 거리를 계산하면서 구하는 것이다.

  거리를 구하기 위해서는 이전 좌표를 알고 있어야 한다.

  이전 좌표라는 것은 이전에 방문한 고객의 집의 좌표를 알고 있어야 한다.

  쉽게 이야기해서 A 고객의 집에서 B 고객의 집으로 간다고 가정했을 때, A의 좌표와 B의 좌표를 알고 있어야만 거리가 계산이

  가능하다. 그래서, 본인은 이전좌표를 순열을 구하기 위한 DFS함수에 매개변수로 두었다.

  그럼 첫 고객의 집은 어떻게 될까 ?? 예를 들어서 회사 - A - B - C - 집 의 루트로 간다고 했을 때, A - B - C 중에서

  가장 처음에 'A'를 뽑았을 떄, 이전 좌표는 ? 회사가 된다. 즉, 가장 처음 DFS를 호출할 때에는 '이전좌표'의 매개변수에

  회사의 좌표를 입력해 주면 된다.

  그 후에, 고객의 집의 수 만큼 수열을 뽑았고 뽑는 동시에 거리까지 계산을 다했다면 ?? 마지막으로 집으로 가는 길만

  따로 계산을 해주면 된다.

  이런 식으로 계산을 해주면서 순열을 뽑는 식으로 구현을 하였다.

  추가적으로, '현재까지 계산한 거리가 지금까지 갱신된 정답보다 크다' 면 더이상 뽑지 않고 종료시켜주었다.

  예를 들어서, 회사 - A - B- C - 집 의 거리가 총 100이라는 경로가 나왔다고 가정해보자.

  그런데, 그 다음 회사 - A - C - B 까지만 구했는데도 이미 105라는 경로라면 이 경우는 계산해줄 필요가 있을까?

  집으로 다시 돌아오는 계산을 해보지 않더라도 절대로 최소거리가 될 수 없다.

  따라서 이런 경우 순열을 더 이상 뽑지 않는 식으로 구현해 주었다.

  다시 한번 말하지만, 위에서 본인이 설명한 시간을 줄일 수 있는 이러한 방법들 쓰시지 않고, 순열만 구하고, 구한 순열대로

  거리를 다 구하고 정답을 도출하더라도, 시간이 오래걸릴 뿐 pass를 받을 수는 있습니다 !

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define MAX 10
#define endl "\n"
using namespace std;
 
int N, Answer;
pair<int, int> Company, House;
vector<pair<int, int>> Customer;
 
bool Select[MAX];
vector<int> V;
 
void Initialize()
{
    memset(Select, false, sizeof(Select));
    Customer.clear();
    Answer = 987654321;
}
 
void Input()
{
    cin >> N;
    cin >> Company.first >> Company.second;
    cin >> House.first >> House.second;
    for (int i = 0; i < N; i++)
    {
        int a, b;
        cin >> a >> b;
        Customer.push_back(make_pair(a, b));
    }
}
 
int Dist(int x, int y, int xx, int yy)
{
    return (abs(x - xx) + abs(y - yy));
}
 
void Calculate(int Custom_Distance)
{
    int Sum = Custom_Distance;
    Sum = Sum + Dist(Customer[V[N - 1]].first, Customer[V[N - 1]].second, House.first, House.second);
 
    if (Answer > Sum) Answer = Sum;
}
 
void DFS(int Cnt, int Px, int Py, int Distance)
{
    if (Distance > Answer) return;
    if (Cnt == N)
    {
        Calculate(Distance);
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(i);
        if (Px == -1 && Py == -1) DFS(Cnt + 1, Customer[i].first, Customer[i].second, Distance);
        else
        {
            int Temp_Dist = Dist(Px, Py, Customer[i].first, Customer[i].second);
            DFS(Cnt + 1, Customer[i].first, Customer[i].second, Distance + Temp_Dist);
        }
        V.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0, Company.first, Company.second, 0);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}