프로그래머스

프로그래머스 여행경로 풀이: 사전순 DFS와 후위 경로 구성

2026년 9월 13일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 여행경로
출처: 프로그래머스 코딩테스트 연습, 깊이/너비 우선 탐색(DFS/BFS)
자체 판단 난이도: Level 3

항공권을 하나도 남기지 않고 모두 사용해야 하며, 가능한 경로가 여러 개이면 전체 경로가 사전순으로 가장 앞서야 한다. 단순히 다음 공항을 사전순으로 고르는 것만으로는 막다른 경로가 생길 수 있어 모든 간선을 사용하는 DFS와 후위 경로 구성이 필요하므로 Level 3으로 판단했다.

1. 문제 요약

출발 공항이 항상 ICN인 항공권 목록 tickets가 주어진다. 각 항공권 [a, b]는 a에서 b로 이동할 수 있다는 뜻이며, 모든 항공권을 정확히 한 번씩 사용해 여행 경로를 만들어야 한다.

가능한 경로가 여러 개라면 공항 이름을 순서대로 비교했을 때 사전순으로 가장 앞서는 경로를 반환한다. 공항 수는 3개 이상 10,000개 이하이고, 모든 항공권을 사용하는 경로가 존재한다.

예를 들어 다음 경로는 항공권 3장을 모두 사용한다.

ICN -> JFK -> HND -> IAD

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그래프 구조와 방문 기록

공항을 정점, 항공권을 방향 간선으로 보는 그래프 문제다. 같은 출발지에서 여러 목적지로 갈 수 있으므로 출발지별 목적지 목록을 인접 리스트로 저장한다.

각 출발지의 목적지를 사전순 내림차순으로 정렬한 뒤 마지막 원소를 pop()한다. 그러면 힙을 사용하지 않고도 항상 사전순으로 가장 앞선 목적지를 꺼낼 수 있다.

graph[출발지] = [목적지 ...]  # 내림차순
next = graph[현재].pop()      # 가장 작은 목적지

후위 경로 구성

현재 공항에서 더 사용할 항공권이 없으면 해당 공항을 route에 추가한다. 항공권을 사용하는 순서가 아니라, 더 이상 진행할 수 없는 공항부터 경로에 들어가므로 결과는 거꾸로 쌓인다. 모든 탐색이 끝난 뒤 route[::-1]을 반환한다.

이 방식은 오일러 경로를 구성하는 Hierholzer 방식과 같다. 어떤 선택이 먼저 막다른 곳에 도착하더라도 그 공항을 바로 최종 경로의 앞쪽에 확정하지 않고 후위에 기록하므로, 남은 간선을 다른 위치에 삽입할 수 있다.

막다른 공항을 후위에 기록해야 하는 이유

사전순으로 가장 작은 목적지를 무조건 즉시 경로에 확정하면 모든 항공권을 사용하지 못할 수 있다. 따라서 DFS 중간의 path를 정답으로 확정하지 않고, 현재 공항에서 더 이상 사용할 간선이 없을 때만 후위 목록에 추가해야 한다.

예를 들어 다음 항공권에서 ICN -> A를 먼저 선택하면 A에서 끝나고 B -> ICN 항공권이 남는다.

ICN -> A
ICN -> B
B -> ICN

실제 유효한 경로는 ICN -> B -> ICN -> A다. 역순 목적지 목록에서 작은 목적지를 꺼내는 DFS와 후위 기록을 함께 사용하면, 처음 선택이 막다른 곳이어도 올바른 위치에 A를 배치할 수 있다.

상태 전이와 경계 처리

스택의 top을 현재 공항으로 사용한다.

현재 공항에 남은 목적지가 있으면 사전순으로 가장 작은 목적지를 꺼내 스택에 넣는다.
남은 목적지가 없으면 현재 공항을 결과 목록에 추가하고 스택에서 제거한다.
스택이 빌 때까지 반복한다.
후위 순서로 쌓인 결과를 뒤집는다.

목적지를 pop()하는 순간 해당 항공권을 사용 처리하므로 별도의 방문 배열이 필요하지 않다. 같은 출발지와 도착지를 가진 항공권이 여러 개라면 목적지 목록에 같은 문자열이 여러 번 들어가고 각각 한 번씩 pop된다.

오답 접근과 반례

현재 공항에서 사전순으로 가장 앞선 항공권을 선택하고 그 경로를 즉시 반환하면, 앞서 본 반례처럼 막다른 공항 때문에 항공권을 남길 수 있다.

tickets = [["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]

ICN -> A는 사전순으로 먼저지만 이 선택만으로 경로를 확정하면 B -> ICN을 사용할 수 없다. 단순한 백트래킹으로 모든 경로를 저장한 뒤 정렬하는 방식도 가능하지만, 항공권이 10,000장일 때 가능한 경로가 매우 많아질 수 있다. 후위 경로 구성은 사용한 간선을 한 번씩만 처리한다.

또한 목적지를 오름차순으로 정렬한 뒤 pop()하면 가장 큰 공항부터 선택하게 된다. pop()을 사용할 때는 내림차순 정렬이 필요하다.

시간·공간 복잡도

모든 항공권을 목적지 목록에 넣고 정렬하므로 전체 정렬 시간은 O(E log E) 이하다. DFS에서 각 항공권을 한 번씩 pop하므로 탐색 시간은 O(E)다. 여기서 E는 항공권 수다.

인접 리스트와 스택, 결과 목록에 항공권 수에 비례하는 공간을 사용하므로 공간 복잡도는 O(E)다.

3. 문제 해결 코드 (Python)

from collections import defaultdict


def solution(tickets):
    graph = defaultdict(list)

    for start, end in tickets:
        graph[start].append(end)

    for destinations in graph.values():
        destinations.sort(reverse=True)

    stack = ["ICN"]
    route = []

    while stack:
        current = stack[-1]

        if graph[current]:
            stack.append(graph[current].pop())
        else:
            route.append(stack.pop())

    return route[::-1]

defaultdict(list)를 사용하면 도착지가 없는 공항에 도착해도 빈 목록처럼 처리할 수 있다. 스택에서 공항을 제거하는 시점이 모든 간선을 소진한 시점이므로, route에는 항상 후위 순서가 저장된다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 모든 항공권 사용과 사전순 경로를 확인할 수 있다.

assert solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]) == ["ICN", "JFK", "HND", "IAD"]
assert solution([["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]) == ["ICN", "B", "ICN", "A"]

4. 공식 예제와 추가 검증

공식 예제와 사전순 선택이 막다른 경로를 만드는 경우, 순환 경로를 Python 코드로 실행했다. 각 경로가 항공권 수보다 하나 많은 공항을 포함하는지도 확인했다.

공식 예제

입력	기대 출력	확인 결과
`[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]`	`["ICN", "JFK", "HND", "IAD"]`	통과
`[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]`	`["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]`	통과

추가 검증 1: 사전순으로 작은 선택이 먼저 막히는 경우

입력: [["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]
기대 출력: ["ICN", "B", "ICN", "A"]
확인 결과: 통과
검증 목적: 후위 경로 구성으로 막다른 공항을 올바른 위치에 배치하는지 확인

추가 검증 2: 순환 경로

입력: [["ICN", "AAA"], ["AAA", "ICN"]]
기대 출력: ["ICN", "AAA", "ICN"]
확인 결과: 통과
검증 목적: 출발 공항으로 돌아오는 순환 간선을 모두 사용하는지 확인

5. 다른 풀이 방식 검색 및 비교

프로그래머스 공식 문제는 ICN에서 출발해 모든 항공권을 사용하고 사전순으로 가장 앞선 경로를 요구한다.
soopy368의 여행경로 DFS 풀이는 목적지를 역순 정렬한 뒤 스택에서 작은 목적지를 꺼내고, 막다른 공항을 후위에 기록하는 접근을 설명한다.

모든 경로를 재귀 백트래킹으로 생성한 뒤 사전순으로 정렬하는 방식은 문제를 직접적으로 이해하기 쉽지만 경로 후보가 많아질 수 있다. 이 글에서는 항공권을 한 번씩만 소비하고 후위 경로를 뒤집는 방식으로 O(E log E)에 처리했다. 재귀 DFS보다 명시적인 스택을 사용해 항공권 수가 10,000개인 입력에서도 Python 재귀 깊이 제한을 피한다.

마무리

여행경로는 현재 선택의 사전순만 보고 경로를 확정하면 안 되는 그래프 문제다. 출발지별 목적지를 정렬하고 항공권을 하나씩 소비하되, 더 이상 갈 곳이 없는 공항을 후위에 기록하면 모든 항공권을 사용하는 경로를 구성할 수 있다. 마지막에 결과를 뒤집는 것이 이 풀이의 핵심이다.