프로그래머스 - 여행경로 (C++)

Pixabay로부터 입수된 Rudy and Peter Skitterians님의 이미지 입니다.

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 이번 문제는 출발 공항, 도착 공항 정보가 있는 항공권들이 주어졌을 때, 모든 항공권을 이용했을 때의 공항 순서를 구하는 문제이다. 그리고 출발 공항은 항상 ICN으로 고정되어 있다. 현재 항공권의 도착 공항과 다음 항공권의 출발 공항이 같아야 하며, 모든 항공권을 이용해야 한다는 점을 고려하면 순열 비슷하게 풀 수 있을 것이다. 예를 들어, 현재 (항공권의 도착) 공항을 기준으로 모든 항공권을 검사한다. 만약 어떤 항공권이 이용한 적 없는 항공권이면서 시작 공항이 현재 공항과 같다면 그 항공권을 다음 항공권으로 이용할 수 있을 것이다. 그리고 모든 항공권을 다 이용한 경우, 항공권 순서에 따른 공항들의 순서를 저장하면 될 것이다.

 그런데 여기서 한 가지 신경써야 할 점이 있는데 그것은 '만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.'라는 문제 조건이다. 그렇기에 단순히 모든 항공권을 다 이용했다고 답을 갱신한다면 2번 예제같이 틀리게 된다. 이를 방지하기 위해 답을 저장/갱신하기 전, 알파벳 순서를 비교하는 과정을 추가해야 한다. 이것들을 고려한 과정은 다음과 같다.

1. 항공권 중 출발 공항이 ICN인 경우, 이 항공권을 시작으로 항공권 순서를 검사한다.
2. 모든 항공권을 검사한다. 만약 현재 (항공권의 도착) 항공과 어떤 항공권의 출발 항공이 같은 경우, 해당 항공권을 항공권 순서를 저장하는 곳(ticketsOrder)에 순서대로 저장한 후, 탐색을 진행한다.
3. 만약 항공권 순서를 저장하는 곳(ticketsOrder)의 크기가 모든 항공권의 개수(크기)와 일치하다면, 현재 항공권들 순서에 따른 공항 순서(airports)를 알아낸다.
4. 만약 답(answer)에 아무것도 저장이 되어 있지 않거나, 만약 답에 저장되어 있는 항공권 순서보다 현재 공항 순서의 알파벳 순서가 더 빠르다면 답을 갱신한다.

#include <string>
#include <vector>
#define MAX 10000000
#define START "ICN"
using namespace std;

bool used[MAX];
vector<vector<string>> allTickets;
vector<int> ticketsOrder;
vector<string> answer;

bool CanUpdate(vector<string> airports)
{
    if (answer.size() == 0)
        return true;
    
    for (int i = 0; i < answer.size(); ++i)
    {
        if (airports[i] < answer[i])
            return true;
        else if (airports[i] > answer[i])
            return false;
    }
    
    return false;
}

void Check(string airport)
{
    if (ticketsOrder.size() == allTickets.size())
    {
        vector<string> airports;
        
        airports.push_back(START);
        
        for (int i = 0; i < ticketsOrder.size(); ++i)
        {
            int ticket = ticketsOrder[i];
            airports.push_back(allTickets[ticket][1]);
        }
        
        if (CanUpdate(airports))
            answer = airports;
        
        return;
    }
    
    for (int i = 0; i < allTickets.size(); ++i)
    {
        if (used[i] == false)
        {
            vector<string> ticket = allTickets[i];
            string departure = ticket[0];
            string arrival = ticket[1];

            if (airport == departure)
            {
                ticketsOrder.push_back(i);
                used[i] = true;
                
                Check(arrival);
                
                used[i] = false;
                ticketsOrder.pop_back();
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    allTickets = tickets;
    
    for (int i = 0; i < allTickets.size(); ++i)
    {
        if (allTickets[i][0] == START)
        {
            used[i] = true;
            ticketsOrder.push_back(i);
            
            Check(allTickets[i][1]);
            
            ticketsOrder.pop_back();
            used[i] = false;
        }
    }
    
    return answer;
}