C++로 티켓 목록에서 여정 경로 찾기

출발 공항과 도착 공항의 쌍 [from, to] 형태로 표현된 티켓 목록이 있다고 가정해 봅시다. 우리는 이 티켓들을 모두 사용하여 올바른 순서의 여정을 찾아야 합니다. 모든 티켓은 첸나이(Chennai)에서 출발하는 한 사람의 것이므로, 여정은 반드시 첸나이에서 시작해야 합니다.

예를 들어 입력이 [["Mumbai", "Kolkata"], ["Chennai", "Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", "Delhi"]]라면, 출력은 ["Chennai", "Mumbai", "Kolkata", "Delhi", "Bangalore"]가 됩니다.

문제 해결 접근 방식

이 문제는 오일러 경로(Eulerian Path)를 찾는 문제로, DFS와 후위 순회(post-order traversal)를 이용한 Hierholzer 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 결과를 저장할 배열 ret과 그래프를 저장할 맵 graph를 정의합니다.
• 공항 이름을 입력으로 받는 visit 메서드를 정의합니다.
• graph[airport]의 크기가 0이 아닌 동안 다음을 반복합니다.
  • x에 graph[airport]의 첫 번째(사전순으로 가장 작은) 요소를 저장합니다.
  • graph[airport]에서 해당 요소를 삭제합니다.
  • visit(x)를 재귀 호출합니다.
• 더 이상 갈 곳이 없으면 현재 공항을 ret에 추가합니다.

메인 함수의 처리 과정

• 티켓 배열의 크기만큼 반복하면서 u = tickets[i][0], v = tickets[i][1]로 설정하고, v를 graph[u]에 삽입합니다.
• 출발 공항인 visit("Chennai")를 호출합니다.
• 최종적으로 ret 리스트를 뒤집어 반환합니다. 역방향으로 기록되기 때문입니다.

C++ 구현 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector <string> ret;
    map < string, multiset <string> > graph;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(int i = 0; i < tickets.size(); i++){
            string u = tickets[i][0];
            string v = tickets[i][1];
            graph[u].insert(v);
        }
        visit("Chennai");
        reverse(ret.begin(), ret.end());
        return ret;
    }
    void visit(string airport){
        while(graph[airport].size()){
            string x = *(graph[airport].begin());
            graph[airport].erase(graph[airport].begin());
            visit(x);
        }
        ret.push_back(airport);
    }
};
main(){
    Solution ob;
    vector<vector<string>> v = {{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}};
    print_vector(ob.findItinerary(v));
}

입력

{{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}

출력

[Chennai, Mumbai, Kolkata, Delhi, Bangalore]

동작 원리 정리

여기서 multiset을 사용하면 같은 노선의 티켓이 여러 장 있어도 자동으로 사전순 정렬이 유지됩니다. 따라서 가능한 경로가 여러 개일 때 항상 사전순으로 가장 앞서는 여정을 얻을 수 있습니다. 각 공항에서 더 이상 사용할 수 있는 티켓이 없을 때 결과에 공항을 기록하고, 마지막에 리스트를 뒤집으면 전체 여정이 올바른 순서로 완성됩니다. 시간 복잡도는 티켓 수를 E라고 할 때 O(E log E)입니다.