[1일 1알고] 여행경로

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

프로그래머스

 

공항의 수가 최대 10000개이기 때문에 최악의 경우 애매한 측면이 있지만, 그래도 기본적으로 ICN에서 시작한다는 점과, 처음 만난 경로이후 탐색할 필요가 없다는점, 반드시 경로는 존재한다는 점을 통해 일단 dfs 백트래킹을 통해 해결해보았습니다.

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int N;
bool isCompleted = false;
vector<string> result;
void dfs(map<string, vector<pair<string, bool>>>& airportMap, vector<string>& answer,
    string curAirport,
    int depth)
{
    if (isCompleted)
        return;
    if (depth == N)
    {
        isCompleted = true;
        result = answer;
        return;
    }

    for (auto& nextAirports : airportMap[curAirport])
    {
        if (!nextAirports.second)
        {
            nextAirports.second = true;
            answer.push_back(nextAirports.first);
            dfs(airportMap, answer, nextAirports.first, depth + 1);
            answer.pop_back();
            nextAirports.second = false;
        }
    }
}

// 항상 ICN에서 출발, 알파벳 순서의 경로
vector<string> solution(vector<vector<string>> tickets) {
    N = tickets.size();

    vector<string> answer;
    map<string, vector<pair<string, bool>>> airportMap;

    for (auto& ticket : tickets)
    {
        airportMap[ticket[0]].push_back({ ticket[1], false });
    }

    for (auto& elem : airportMap)
    {
        sort(elem.second.begin(), elem.second.end());
    }

    answer.push_back("ICN");
    dfs(airportMap, answer, "ICN", 0);


    return result;
}

dfs 내부에서 필요한 조건은 현재 공항에서 다음 공항으로 가기 위한 경로들, 현재 공항 위치, depth(소모한 티켓 수)

, 전체 티켓의 수 정도가 있을 것입니다.

 

재귀함수 내부 처리는 일반적인 dfs처럼 처리했습니다.

 

그리고 또 중요한 점은 사전순으로 정답을 구하기 때문에 미리 정렬을 해놓는 것입니다.

그리고 추가적으로 map내부의 value를 string과 bool의 pair로 만들어 visited 배열을 별도로 만들지 않고 처리했습니다.

 

---

해당 문제를 검증하는 예시는 4개로 통과하긴했지만 불충분해보입니다. 

 

요즘은 문제를 일단 직접 풀어보고, 이후에 더 좋은 알고리즘이 있을지 ai에게 물어보는 편입니다.

앞으로는 이런 내용도 소개하려고 합니다. 

 

일단 이 문제를 다시 해석하면 노드 사이에 모든 간선을 소모하여 경로를 구하는 문제입니다.

이는 오일러 경로를 구하는 것과 같습니다. 쉽게 표현하면 한붓그리기의 경로를 찾는 것입니다.

https://en.wikipedia.org/wiki/Eulerian_path

 

한붓그리기는 노드의 상태에 따라 불가능한 경우도 있으나, 기본 조건이 경로는 존재한다이기 때문에 이를 배제할 수 있습니다.

 

오일러 경로를 구하는 Hierholzer를 사용하면 이전보다 더 효율적으로 탐색이 가능하게 됩니다.

 

Hierholzer알고리즘은 오일러 경로를 말단부터 확정하는 알고리즘입니다.

해당 문제라면 ticket(간선)을 탐색할 때 백트래킹처럼 티켓을 소비하고 다시 복구하는 것이 아닌

그냥 티켓을 사용하면 소모해버립니다. 

 

그리고 이후 현재 위치에서 더이상 갈 수 없는 경우가 생긴다면 그 때 result에 추가합니다.

결론적으로 한붓그리기의 말단부터 확장해나가는 것입니다. 

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<string> result;

void dfs(map<string, vector<string>>& airportMap, string curAirport)
{
    auto& nextAirports = airportMap[curAirport];

    while (!nextAirports.empty())
    {
        string nextAirport = nextAirports.back();
        nextAirports.pop_back();   // 항공권 소모

        dfs(airportMap, nextAirport);
    }

    result.push_back(curAirport);
}

vector<string> solution(vector<vector<string>> tickets)
{
    result.clear();

    map<string, vector<string>> airportMap;

    for (auto& ticket : tickets)
    {
        airportMap[ticket[0]].push_back(ticket[1]);
    }

    for (auto& elem : airportMap)
    {
        sort(elem.second.rbegin(), elem.second.rend());
    }

    dfs(airportMap, "ICN");

    reverse(result.begin(), result.end());

    return result;
}

 

복습하지 않는다면 까먹을 확률이 높겠네요