C++ Hierholzer 알고리즘으로 항공 여행 경로의 올바른 순서 찾기

출발 공항과 도착 공항의 쌍 [from, to]으로 표현된 항공권 목록이 주어졌을 때, 이를 올바른 순서대로 재구성하여 전체 여행 일정을 완성하는 것이 이번 글의 목표입니다. 모든 항공권은 KLK 공항에서 출발하는 한 사람의 소유이므로, 재구성된 여행 일정은 반드시 KLK에서 시작해야 합니다.

예를 들어 입력이 [["MUC", "LHR"], ["KLK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]라면, 출력은 ["KLK", "MUC", "LHR", "SFO", "SJC"]가 됩니다.

문제 해결 접근 방식

이 문제는 그래프 이론에서 오일러 경로(Eulerian Path)를 찾는 것과 본질적으로 같으며, Hierholzer 알고리즘을 활용하면 깊이 우선 탐색(DFS) 기반으로 효율적으로 해결할 수 있습니다. 각 공항을 노드로, 항공권을 간선으로 생각하고, 가능한 한 사전순으로 앞서는 목적지를 우선 방문하도록 구성하면 됩니다.

알고리즘 단계

결과를 저장할 배열 ret과 그래프 정보를 담을 맵 graph를 정의합니다.
공항 이름을 인자로 받는 visit 메서드를 정의합니다.
graph[airport]의 크기가 0이 아닌 동안 다음을 반복합니다.
- x := graph[airport]의 첫 번째 원소
- graph[airport]에서 해당 원소를 삭제
- visit(x) 재귀 호출
반복이 끝나면 ret에 현재 공항을 추가합니다.
메인 함수에서는 다음을 수행합니다.
- i를 0부터 tickets 배열 크기까지 순회하며 u := tickets[i][0], v := tickets[i][1]로 두고 graph[u]에 v를 삽입합니다.
출발 공항인 KLK부터 visit("KLK")를 호출합니다.
최종적으로 ret 리스트를 뒤집어 반환합니다.

여기서 multiset을 사용하면 같은 구간의 항공권이 여러 장 있더라도 중복을 허용하면서 자동으로 사전순 정렬이 유지되므로, 항상 가장 작은 순서의 목적지부터 방문할 수 있다는 장점이 있습니다.

예제 코드

#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("KLK");
      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 ={{"MUC","LHR"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
   print_vector(ob.findItinerary(v));
}

입력

{{"MUC","LHR"},{"KLK","MUC"},{"SFO","SJC"},{"LHR","SFO"}}

출력

[KLK, MUC, LHR, SFO, SJC]

동작 원리 요약

visit 함수는 현재 공항에서 출발하는 항공권이 남아 있는 동안 계속 더 깊이 이동하는 재귀적 DFS입니다. 더 이상 갈 곳이 없는 공항(막다른 길)에 도달하면 그 공항을 결과에 기록하고 되돌아오는데, 이렇게 기록된 순서는 실제 여행 순서의 역순이므로 마지막에 reverse로 뒤집어 주면 최종 일정이 완성됩니다. 이 방식의 시간 복잡도는 항공권 수에 대해 선형적인 O(N log N) 수준으로 매우 효율적입니다.