비행 노선이 [출발지, 도착지] 쌍으로 이루어진 리스트로 주어진다고 가정해 보겠습니다. 이 리스트는 뒤섞여 있어 순서를 알 수 없으며, 우리는 모든 공항을 실제 방문 순서대로 찾아야 합니다. 만약 유효한 여정이 두 개 이상 존재한다면, 사전순(lexicographically)으로 가장 작은 경로를 반환해야 합니다.
예를 들어 입력이 다음과 같다면,
flights = [["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]]
출력은 다음과 같습니다.
['Delhi', 'Mumbai', 'Kolkata', 'Delhi']
문제의 본질: 오일러 경로(Eulerian Path)
이 문제는 그래프 이론의 오일러 경로 찾기와 본질적으로 동일합니다. 각 공항은 그래프의 정점(vertex)이 되고, 각 항공편은 간선(edge)이 됩니다. 오일러 경로란 모든 간선을 정확히 한 번씩만 통과하는 경로를 의미합니다.
오일러 경로가 존재하려면 다음 조건을 만족해야 합니다.
- 출발점 후보: 나가는 간선 수에서 들어오는 간선 수를 뺀 값(outs − ins)이 1인 정점은 최대 하나만 존재해야 합니다.
- 도착점 후보: outs − ins가 −1인 정점 역시 최대 하나만 존재해야 합니다.
- 나머지 정점: 들어오는 간선과 나가는 간선의 수가 같아야 합니다(outs − ins = 0).
모든 정점에서 outs − ins가 0이라면 그래프에는 오일러 회로(Eulerian Circuit)가 존재하며, 어느 정점에서 시작해도 무방합니다. 이 경우 사전순 조건을 만족하기 위해 이름이 가장 작은 공항에서 출발합니다.
해결 단계
- 자료 구조 초기화: ins(도착 횟수), outs(출발 횟수), adj_list(인접 리스트) 세 개의 맵을 준비합니다.
- 그래프 구성: flights의 각 (s, e) 쌍에 대해 adj_list[s]에 e를 추가하고, outs[s]와 ins[e]를 각각 1씩 증가시킵니다.
- 사전순 보장: adj_list의 모든 인접 리스트를 정렬합니다. 이렇게 하면 탐색 시 항상 사전순으로 앞서는 공항을 먼저 방문하게 됩니다.
- 시작점·끝점 판별: 모든 공항을 검사하여 outs − ins가 1이면 start로, −1이면 end로 지정합니다. 해당하는 정점이 둘 이상이거나 균형이 맞지 않으면 유효한 경로가 없으므로 종료합니다.
- 시작점 결정: start가 없다면(오일러 회로인 경우) adj_list의 키 중 최솟값을 시작점으로 삼습니다.
- DFS 탐색(히어홀처 알고리즘): dfs() 함수는 현재 공항에서 아직 사용하지 않은 간선이 남아 있는 동안 다음 공항으로 재귀적으로 이동합니다. 이때 다음에 방문할 이웃의 인덱스는
nxt = len(adj_list[airport]) - outs[airport]로 계산하고, 매번 outs[airport]를 1씩 감소시켜 사용한 간선을 추적합니다. 더 이상 나갈 간선이 없으면 현재 공항을 ans 리스트 끝에 추가합니다. - 결과 반환: ans는 역순으로 쌓이므로, 메인 메서드에서 solve(flights)를 호출한 뒤 마지막에 리스트를 뒤집어 반환합니다.
Python 구현 예제
from collections import defaultdict
class Solution:
def solve(self, flights):
ins = defaultdict(int)
outs = defaultdict(int)
adj_list = defaultdict(list)
for s, e in flights:
adj_list[s].append(e)
outs[s] += 1
ins[e] += 1
for l in adj_list.values():
l.sort()
start = None
end = None
for airport in adj_list.keys():
if outs[airport] - ins[airport] == 1:
if start:
return
start = airport
elif outs[airport] - ins[airport] == -1:
if end:
return
end = airport
elif outs[airport] - ins[airport] != 0:
return
start = start if start else min(adj_list.keys())
ans = []
def dfs(airport):
while outs[airport]:
nxt = len(adj_list[airport]) - outs[airport]
outs[airport] -= 1
dfs(adj_list[airport][nxt])
ans.append(airport)
dfs(start)
return ans[::-1]
ob = Solution()
flights = [
["Mumbai", "Kolkata"],
["Delhi", "Mumbai"],
["Kolkata", "Delhi"]
]
print(ob.solve(flights))
입력
[["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]]
출력
['Delhi', 'Mumbai', 'Kolkata', 'Delhi']
동작 원리 살펴보기
예제 입력에서 각 공항의 간선 정보는 다음과 같습니다.
- Mumbai → Kolkata (출발 1회, 도착 1회)
- Delhi → Mumbai (출발 1회, 도착 1회)
- Kolkata → Delhi (출발 1회, 도착 1회)
모든 공항에서 들어오는 간선과 나가는 간선의 수가 같으므로 이 그래프에는 오일러 회로가 존재합니다. 따라서 사전순으로 가장 작은 공항인 'Delhi'에서 탐색을 시작하며, 결과적으로 ['Delhi', 'Mumbai', 'Kolkata', 'Delhi']라는 경로를 얻게 됩니다.
성능 측면에서 인접 리스트 정렬에 O(E log E)의 비용이 들며, DFS 탐색 자체는 간선 수 E, 정점 수 V에 대해 O(E + V)로 매우 효율적입니다.