출발 공항과 도착 공항의 쌍 [from, to] 형태로 표현된 항공권 목록이 주어졌다고 가정해 봅시다. 우리는 이 항공권들을 모두 사용해 여정을 올바른 순서대로 재구성해야 합니다. 모든 항공권은 JFK에서 출발하는 한 사람의 소유이므로, 완성된 여정은 반드시 JFK에서 시작해야 합니다.
예를 들어 입력이 [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]라면, 출력은 ["JFK", "MUC", "LHR", "SFO", "SJC"]가 됩니다.
문제 해결 접근 방법
이 문제는 본질적으로 오일러 경로(Eulerian Path)를 찾는 문제이며, 깊이 우선 탐색(DFS)과 백트래킹 개념을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 간선(항공권)을 정확히 한 번씩만 사용하면서 경로를 완성하는 것입니다.
다음 단계에 따라 진행합니다:
- 결과를 저장할 배열
ret과 인접 공항 정보를 담을 맵graph를 정의합니다. - 공항 이름을 입력으로 받는
visit메서드를 정의합니다. graph[airport]의 크기가 0이 아닌 동안 다음을 반복합니다:x := graph[airport]의 첫 번째 원소graph[airport]에서 해당 원소를 삭제visit(x)재귀 호출
- 반복이 끝나면 현재
airport를ret에 추가합니다. - 메인 메서드에서는 다음을 수행합니다:
i를 0부터 tickets 배열의 크기까지 반복하며:u := tickets[i][0],v := tickets[i][1]로 설정하고v를graph[u]에 삽입
- 첫 공항이므로
visit("JFK")를 호출합니다. - 최종적으로
ret리스트를 뒤집어 반환합니다.
핵심 포인트
multiset을 사용하면 같은 출발지에서 여러 목적지로 향하는 항공권이 있을 때 자동으로 사전순(lexicographical order)으로 정렬되므로, 가능한 여정 중 사전순으로 가장 앞서는 결과를 보장할 수 있습니다. 또한 DFS가 종착지부터 역순으로 공항을 기록하기 때문에 마지막에 리스트를 뒤집어야 올바른 순서의 여정이 완성됩니다.
예제 코드(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("JFK");
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"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
print_vector(ob.findItinerary(v));
}입력
[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
출력
[JFK, MUC, LHR, SFO, SJC]