[프로그래머스] 여행경로 - Level 3 (Python)

📌 문제 정보

여행경로 Level 3

플랫폼

프로그래머스

유형

DFS, 백트래킹

언어

Python 3

풀이 시간

약 60분

풀이 날짜

2026.06.28

문제 링크

바로가기 ↗

---

🧩 문제 요약

주어진 항공권(tickets) 배열을 모두 사용해 ICN에서 출발하는 여행 경로를 반환하는 문제

명령 조건:

• 항상 ICN에서 출발
• 모든 티켓을 반드시 사용해야 함
• 가능한 경로가 여러 개이면 알파벳 오름차순으로 반환

입력 조건:

• 항공권 수: 1 ≤ tickets의 길이 ≤ 10,000
• 모든 공항은 알파벳 대문자 3글자
• 모든 도시를 방문할 수 없는 경우는 주어지지 않음

출력 조건:

• 방문한 공항 경로를 담은 배열 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

defaultdict(list)로 그래프를 만들고, 단순 DFS로 경로를 탐색했다. sort(reverse=True) 후 pop()으로 알파벳 오름차순을 보장하려 했으나, 막혔을 때 되돌아오는 로직이 없어 일부 케이스에서 실패했다.

2단계 - 막혔던 부분

백트래킹을 구현하기 위해 sort(reverse=True) + pop() + append() 조합을 시도했다. 그러나 되돌릴 때 append()로 다시 넣으면 이미 역정렬된 리스트 끝에 추가되므로 pop() 시 똑같은 노드가 반복해서 나오는 무한루프 문제가 발생했다.

3단계 - 해결 실마리

sort() (오름차순) + pop(i) + insert(i, node) 조합으로 해결했다. pop(i)로 i번째 노드를 꺼내고, 실패 시 insert(i, node)로 정확히 같은 자리에 되돌리면 무한루프 없이 백트래킹이 가능하다는 것을 파악했다.

핵심 아이디어:

• tickets.sort()로 알파벳 오름차순 보장 → for문이 순서대로 시도하므로 첫 번째 성공 경로가 곧 정답
• pop(i) + insert(i, node)로 원상복구 → 정확히 같은 인덱스에 돌려놓아야 무한루프 방지
• return True/False로 성공/실패를 위로 전파 → 성공한 순간 더 이상 탐색 불필요

---

✅ 최종 풀이 코드

from collections import defaultdict

def solution(tickets):
    answer = ["ICN"]
    graph = defaultdict(list)
    for k, v in tickets:
        graph[k].append(v)

    for key in graph:
        graph[key].sort()               # 알파벳 오름차순 정렬

    def dfs(start):
        if len(answer) == len(tickets) + 1:   # 모든 티켓 사용 완료
            return True

        for i in range(len(graph[start])):
            next_node = graph[start].pop(i)   # 선택
            answer.append(next_node)

            if dfs(next_node):
                return True

            graph[start].insert(i, next_node) # 실패 시 원상복구
            answer.pop()

    dfs("ICN")
    return answer

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(N * N!) 최악	정렬 O(N log N) + 백트래킹 최악 O(N * N!), 실제로는 알파벳순 첫 성공 경로에서 종료
공간 복잡도	O(N)	graph, answer, 재귀 스택 모두 티켓 수 N에 비례

tickets의 길이가 최대 10,000이지만, 알파벳 오름차순 정렬 후 첫 번째 성공 경로에서 바로 return True로 종료되므로 실제 탐색량은 훨씬 적다.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	백트래킹 없이 단순 DFS → 막힌 경로에서 되돌아오지 못해 일부 케이스 실패	return True/False로 성공/실패 전파, 실패 시 answer.pop() 추가
2차	sort(reverse=True) + pop() + append() 조합 → 되돌릴 때 같은 노드가 반복 선택되는 무한루프	sort() + pop(i) + insert(i, node)로 변경하여 정확히 같은 자리에 원상복구
3차	통과 ✅	-

---

🔄 다른 풀이 방법

graph 없이 tickets 직접 순회

def solution(tickets):
    tickets.sort()
    visited = [False] * len(tickets)
    answer = ["ICN"]

    def dfs(start):
        if len(answer) == len(tickets) + 1:
            return True

        for i, (f, t) in enumerate(tickets):
            if f == start and not visited[i]:
                visited[i] = True          # 티켓 사용 처리
                answer.append(t)

                if dfs(t):
                    return True

                visited[i] = False         # 실패 시 되돌리기
                answer.pop()

        return False

    dfs("ICN")
    return answer

v1 vs v2 비교:

• v1 (graph 방식): defaultdict로 그래프를 별도 구성, 출발지 이웃만 순회하여 탐색 범위가 좁음
• v2 (tickets 직접 순회): graph 없이 tickets 전체를 매번 순회, 코드가 더 단순하고 visited 배열로 직관적으로 관리

오일러 경로 (Hierholzer 알고리즘)

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]

    for r in routes:
        routes[r].sort(reverse=True)    # pop()으로 알파벳 오름차순 꺼내기

    stack = ["ICN"]
    path = []

    while stack:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:  # 갈 곳 없으면
            path.append(stack.pop())                     # 끝으로 확정
        else:
            stack.append(routes[top].pop())              # 다음 노드 push

    return path[::-1]

백트래킹 DFS vs 오일러 경로:

• DFS: 틀린 선택을 취소하며 되돌아가는 방식, O(N * N!) 최악
• 오일러: "막힌 노드는 무조건 끝"이라는 수학적 사실을 이용, O(N)으로 훨씬 빠름
• 단, 오일러는 경로가 하나일 때만 적용 가능하며 발상을 현장에서 떠올리기 어려움
• 더 자세한 이론은 → DFS 백트래킹 vs 오일러 경로 이론 정리

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: sort(reverse=True) + pop() 조합은 백트래킹과 함께 쓰면 무한루프가 발생한다. 백트래킹할 때는 반드시 pop(i) + insert(i, node)로 정확히 같은 자리에 원상복구해야 한다.
• ✏️ 새로 알게 된 것: 오일러 경로(Hierholzer)는 "막힌 노드를 경로의 끝으로 확정하고 뒤집는" 발상으로, 스택 자체가 되돌아가는 역할을 대신한다. DFS의 재귀 콜스택을 명시적 스택으로 대체한 구조다.
• ⚠️ 실수했던 점: 백트래킹에서 return True/False 전파를 빠뜨려 성공 경로를 찾아도 계속 탐색하는 문제가 있었다. 성공 시 즉시 return True로 끝내야 한다는 것을 놓쳤다.
• 💬 한 줄 요약: 막히는 경우가 있는 DFS는 반드시 백트래킹(선택 취소)을 고려하자. pop(i) + insert(i)가 핵심이다!