[ SWEA 1798 ] 범준이의 제주도 여행 계획 (C++)

SWExpertAcademy의 범준이의 제주도 여행 계획(1798 / D5) 문제이다.

[ 문제풀이 ]

먼저, 문제에서 주어진 여행 계획들의 조건들을 통해서 실질적으로 문제를 풀기 전에, 어떤 부분을 생각해주어야 하고, 어떻게 풀어나갈지 알아보자.

1. 첫날 공항에 도착한 후부터 M일 후 다시 공항에 돌아올 떄 까지 얻은 만족도와 경로를 구해야 한다.

2. 방문할 수 있는 지점은 공항, 호텔, 관광포인트를 모두 합해 N개의 지점이 있다.

3. 각 관광포인트는 즐기기 위해 소요되는 시간과 얻을 수 있는 만족도가 정해져 있으며, 한 번 갔던 관광포인트는

   다시 방문하지 않는다.

- "한 번 갔던 관광포인트는 다시 방문하지 않는다." 라는 문구를 통해서, 우리는 "관광포인트에 대한, 중복된 탐색을 하면

   안된다" 라는 것을 알 수 있고, 이 부분을 관리해 주어야 할 것 같다.

4. 각 지점들은 서로 간에 모두 연결된 길이 있으며, 이동에 소요되는 시간이 정해져 있다. 또 다른 길로 우회하여

   가지 않는다.

5. 하루에 이동 + 놀이에 소요되는 시간이 9시간이 넘으면 안되고 그 전에 반드시 호텔에 입실해야 한다.

- 특정 지점에서, 그 다음 관광포인트로 넘어갈 때 소요되는 시간이 9시간이 넘으면 안되기 때문에, 탐색을 하기 전에

   시간을 고려해서 탐색을 해줘야 한다. 만약, 시간 상, 그 다음 관광포인트로 넘어갈 수 없다면 호텔, 혹은 공항으로

   가는 경로를 고려해야 한다.

6. M일째 날에도 9시간을 사용할 수 있으며 그 전에 공항에 도착해야 한다.

- M번째 날과, M번째가 아닌 날에 대한 구분이 필요하다. M번째 날에는 최종적으로 공항으로 돌아가야 하지만,

  그게 아닌 날에는 최종적으로 호텔에 돌아가야 하기 때문에, 현재날이 'M번째 날'인지 아닌지에 대해서

  구분해주어야 한다.

대략적으로 위에서 몇 가지를 살펴봤는데, 정리해보자.

1. 관광 포인트에 대한 중복된 탐색을 할 수 없으므로, Visit[]를 이용해서 이를 관리해 주어야 한다.

2. 하루에 주어진 시간이 '9시간' 이기 때문에, 시간을 고려해서 관광포인트를 탐색해 주어야 한다.

3. 만약 2번)에서 더 이상 갈 수 없는 관광포인트가 없다면, 호텔 or 공항으로 가는 경로를 탐색해 주어야 한다.

본인은 이 문제를 완전탐색, 완전탐색 중에서도 깊이우선탐색(DFS)를 이용해서 접근하였다.

DFS함수에서 사용된 매개변수는 { 현재 장소 , 날짜 , 만족도 , 시간 , 탐색 깊이 , 경로 } 가 있다.

코드를 보면서 이해해보자.

void DFS(int Cur, int Day, int Satisfy, int Time, int Depth, vector<int>& Route)
{
    if (Cur == Airport && Day == M && Depth != 0)
    {
        if (Satisfy > Answer)
        {
            Answer = Satisfy;
            Answer_Route = Route;
        }
        return;
    }
 
    bool Flag = false;
    for (int i = 0; i < Tour.size(); i++)
    {
        int Next = Tour[i].first;
        int Play_Time = Tour[i].second.first;
        int nSatisfy = Tour[i].second.second;
        int Move_Time = Distance[Cur][Next];
 
        if (Visit[Next] == true || Cur == Next) continue;
        if (Time + Move_Time + Play_Time > 540) continue;
        
        Flag = true;
        Visit[Next] = true;
        Route.push_back(Next);
        DFS(Next, Day, Satisfy + nSatisfy, Time + Move_Time + Play_Time, Depth + 1, Route);
        Route.pop_back();
        Visit[Next] = false;
    }
 
    if (Flag == false)
    {
        if (Day == M)
        {
            if (Time + Distance[Cur][Airport] <= 540)
            {
                Route.push_back(Airport);
                DFS(Airport, Day, Satisfy, Time + Distance[Cur][Airport], Depth + 1, Route);
                Route.pop_back();
            }
        }
        else
        {
            for (int i = 0; i < Hotel.size(); i++)
            {
                int Hotel_Num = Hotel[i];
                if (Time + Distance[Cur][Hotel_Num] <= 540)
                {
                    Route.push_back(Hotel_Num);
                    DFS(Hotel_Num, Day + 1, Satisfy, 0, Depth + 1, Route);
                    Route.pop_back();
                }
            }
        }
    }
}

본인이 구현한 DFS 코드이다.

먼저, line3 ~ 11) 을 최종적으로 M번째 날 다시 공항에 돌아갔을 때, 최종적인 만족도와 경로를 갱신하는 부분이다.

기존의 만족도보다 더 높은 만족도로 여행을 마쳤다면, 그 만족도와 그 경로로 갱신해 주어야 하기 때문이다.

그리고 이 부분을 위해서 매개변수로 "탐색 깊이"를 넣어주었다. 왜냐하면 시작점은 무조건 공항인데, 탐색 깊이에 대한 조건이 붙어있지 않다면, 탐색을 하지도 않고, "현재 지점이 공항이다." 라는 조건 때문에 바로 탐색이 종료될 수 있기 때문이다.

line14 ~ 30) 을 보게되면, 시간을 고려하면서 그 다음 관광포인트를 탐색하는 과정이다.

이미 방문한 지점을 다시 탐색하지 않고, 시간이 되는 관광포인트들만 순차적으로 탐색을 하는 과정이다.

line13) 에서 보면 'Flag'라는 변수가 있는데, 이는 "더 이상 탐색할 수 있는 관광포인트가 있는지 없는지" 를 구분하기 위한 변수이다. 만약, 관광포인트들을 탐색해 봤을 때, 더 이상 탐색할 수 있는 관광포인트가 없다면, M번째 날에는 공항으로, M번째가 아닌 날에는 호텔로 가는 경로를 탐색해봐야 하기 때문에 이를 구분하기 위해서 'Flag'라는 변수를 사용해 주었다.

line32 ~ 56)을 보게 되면, "더 이상 관광포인트를 탐색할 수 없는 경우" 에 해당하는 조건문이다.

위에서도 말했듯이, 이 경우에는 호텔 or 공항으로의 경로를 탐색해 주어야 한다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <vector>
 
#define endl "\n"
#define MAX 40
using namespace std;
 
int N, M, Airport, Answer;
int Distance[MAX][MAX];
bool Visit[MAX];
vector<int> Hotel;
vector<int> Answer_Route;
vector<pair<int, pair<int, int>>> Tour;
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Hotel.clear();
    Answer_Route.clear();
    Tour.clear();
    Answer = 0;
    memset(Visit, false, sizeof(Visit));
    memset(Distance, 0, sizeof(Distance));
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = i + 1; j <= N; j++)
        {
            int a; cin >> a;
            Distance[i][j] = a;
            Distance[j][i] = a;
        }
    }
    for (int i = 1; i <= N; i++)
    {
        char C; cin >> C;
        if (C == 'A') Airport = i;
        else if (C == 'H') Hotel.push_back(i);
        else
        {
            int a, b; cin >> a >> b;
            Tour.push_back(make_pair(i, make_pair(a, b)));
        }
    }
}
 
void DFS(int Cur, int Day, int Satisfy, int Time, int Depth, vector<int>& Route)
{
    if (Cur == Airport && Day == M && Depth != 0)
    {
        if (Satisfy > Answer)
        {
            Answer = Satisfy;
            Answer_Route = Route;
        }
        return;
    }
 
    bool Flag = false;
    for (int i = 0; i < Tour.size(); i++)
    {
        int Next = Tour[i].first;
        int Play_Time = Tour[i].second.first;
        int nSatisfy = Tour[i].second.second;
        int Move_Time = Distance[Cur][Next];
 
        if (Visit[Next] == true || Cur == Next) continue;
        if (Time + Move_Time + Play_Time > 540) continue;
        
        Flag = true;
        Visit[Next] = true;
        Route.push_back(Next);
        DFS(Next, Day, Satisfy + nSatisfy, Time + Move_Time + Play_Time, Depth + 1, Route);
        Route.pop_back();
        Visit[Next] = false;
    }
 
    if (Flag == false)
    {
        if (Day == M)
        {
            if (Time + Distance[Cur][Airport] <= 540)
            {
                Route.push_back(Airport);
                DFS(Airport, Day, Satisfy, Time + Distance[Cur][Airport], Depth + 1, Route);
                Route.pop_back();
            }
        }
        else
        {
            for (int i = 0; i < Hotel.size(); i++)
            {
                int Hotel_Num = Hotel[i];
                if (Time + Distance[Cur][Hotel_Num] <= 540)
                {
                    Route.push_back(Hotel_Num);
                    DFS(Hotel_Num, Day + 1, Satisfy, 0, Depth + 1, Route);
                    Route.pop_back();
                }
            }
        }
    }
}
 
void Solution()
{
    int Start = Airport;
    vector<int> V;
    DFS(Start, 1, 0, 0, 0, V);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
        
        cout << "#" << T << " ";
        cout << Answer << " ";
        if (Answer != 0)
        {
            for (int i = 0; i < Answer_Route.size(); i++)
            {
                cout << Answer_Route[i] << " ";
            }
            cout << endl;
        }
        else cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}