[LeetCode 332] Reconstruct Itinerary (Java)

🚀 문제 분석

• 목표: 주어진 비행기 티켓 목록([from, to])을 모두 사용하여 'JFK' 공항에서 출발하는 여행 일정을 재구성합니다.
• 핵심: 그래프의 모든 간선(Edge)을 정확히 한 번씩 모두 방문하는 오일러 경로(Eulerian Path) 문제입니다.
• 티켓 소모: 모든 티켓을 남김없이 써야 하며, 정점(공항)은 여러 번 방문할 수 있습니다.
• 사전순 정렬: 가능한 경로가 여러 개라면, 알파벳 순서(어휘 순)로 가장 앞서는 경로를 선택해야 합니다.

---

💡 해결 전략: 히르홀저 알고리즘(Hierholzer's Algorithm)과 후위 순회

일반적인 visited 배열이나 백트래킹(티켓 복원) 방식을 사용하면 중복 간선 처리와 시간 초과(TLE) 문제로 코드가 매우 복잡해집니다. 대신 간선 소모와 후위 순회(Post-order)를 활용하는 히르홀저 알고리즘으로 해결합니다.

1. 우선순위 큐 기반 인접 리스트: 사전순으로 앞서는 공항을 먼저 방문하기 위해, 각 출발지별 도착지 목록을 PriorityQueue로 관리합니다.
2. 간선 소모 (poll()): visited 체크 대신, 방문한 간선(티켓)은 poll()로 그래프에서 완전히 제거하여 중복 방문을 차단합니다.
3. 막다른 길(Dead-end) 처리 (후위 순회):

• 사전순 탐색 도중 일찍 막다른 길에 다다르더라도, 더 이상 갈 곳이 없을 때 결과를 맨 앞(addFirst)에 추가합니다.
• 후위 순회 특성상 일찍 갇힌 막다른 노드가 전체 여정의 가장 마지막으로 배치되며, 스쳐 지나온 잔여 티켓(서브 순환 경로)은 되돌아오는 과정에서 자연스럽게 앞쪽에 끼워 맞춰집니다.

---

💻 구현 코드 (Java)

import java.util.*;

public class Solution_Leetcode_332 {

    // 출발지별 도착지들을 사전순(알파벳순)으로 자동 정렬하는 인접 리스트
    private Map<String, PriorityQueue<String>> graph = new HashMap<>();
    // 후위 순회 결과를 역순(앞쪽)으로 삽입하기 위한 Deque
    private Deque<String> ans = new ArrayDeque<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // 1. 그래프 구축 (PriorityQueue를 활용하여 알파벳순 정렬)
        for (List<String> ticket : tickets) {
            graph.putIfAbsent(ticket.get(0), new PriorityQueue<>());
            graph.get(ticket.get(0)).add(ticket.get(1));
        }

        // 2. 'JFK'에서 DFS 탐색 시작
        dfs("JFK");

        // 3. Deque를 List로 변환하여 반환
        return new ArrayList<>(ans);
    }

    private void dfs(String from) {
        PriorityQueue<String> arrivals = graph.getOrDefault(from, new PriorityQueue<>());

        // 출발지에 남은 티켓이 있는 동안 계속 이동 (간선 소모)
        while (!arrivals.isEmpty()) {
            dfs(arrivals.poll());
        }

        // 더 이상 갈 곳이 없으면(막다른 길) 결과를 맨 앞에 추가 (후위 순회)
        ans.addFirst(from);
    }
}

---

🧐 기술적 고찰

• visited 백트래킹 대비 압도적 효율성: 동일한 구간의 티켓이 여러 장일 수 있어 visited 상태 복원 로직을 작성하면 시간 복잡도가 $O(E!)$까지 치솟을 수 있습니다. 반면, 히르홀저 알고리즘은 사용한 간선을 즉시 제거하므로 단 한 번의 DFS로 끝납니다.
• 시간 복잡도: 티켓을 PriorityQueue에 삽입하고 정렬하는 데 $O(E \log E)$, DFS 탐색 시 각 간선을 딱 한 번씩만 poll()하므로 $O(E)$가 소요되어 전체 시간 복잡도는 $O(E \log E)$입니다. ($E$는 티켓의 개수)
• 자료구조의 조화: PriorityQueue로 알파벳 우선순위를 보장하고, ArrayDeque의 addFirst()로 후위 순회의 역순 배치를 깔끔하게 처리한 점이 알고리즘 최적화의 핵심입니다.