a-093-reconstruct-itinerary2026-08-21hardleetcode #332neetcode150

여행 경로 재구성

#array#string#depth-first-search#graph#sorting#heap-priority-queue#eulerian-circuit#eulerian-path#semi-eulerian-graph

↗ leetcode #332 · a-093-reconstruct-itinerary

문제

· problem

P.a-093-reconstruct-itinerary

여행 경로 재구성

항공사 티켓 목록 tickets이 주어지며, 각 tickets[i] = [from_i, to_i]는 한 항공편의 출발지와 도착지 공항을 나타냅니다. 경로를 순서대로 재구성하여 반환하세요. 모든 티켓은 "JFK"에서 출발하는 한 사람에게 속하므로, 경로는 "JFK"로 시작해야 합니다. 유효한 경로가 여러 개 있으면, 단일 문자열로 읽을 때 사전식 순서가 가장 작은 경로를 반환해야 합니다. 예를 들어, 경로 ["JFK", "LGA"]는 ["JFK", "LGB"]보다 사전식 순서가 작습니다. 모든 티켓이 유효한 경로를 형성한다고 가정할 수 있습니다. 각 티켓을 정확히 한 번만 사용해야 합니다.

제약

· 1 ≤ tickets.length ≤ 300
· tickets[i].length == 2
· from_i and to_i consist of uppercase English letters, each of length 3
· from_i ≠ to_i
· All tickets form at least one valid itinerary

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

["JFK","MUC","LHR","SFO","SJC"]

example 2input → output

[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

["JFK","ATL","JFK","SFO","ATL","SFO"]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
모든 티켓을 정확히 한 번씩 사용해야 하나요?
☐
공항이 경로에서 여러 번 나타날 수 있나요?
☐
"사전식 순서가 가장 작다"는 무엇을 의미하나요?
☐
JFK가 아닌 다른 공항에서 출발할 수 있나요?
☐
탐욕 알고리즘으로 각 단계마다 사전식 최소 도착지를 선택하면 되나요?
☐
노드가 아닌 간선(티켓)을 정확히 한 번 사용해야 합니다. 이게 중요한 이유는?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 인접 리스트 초기화 - 모든 출발지 사전 등록

○

adj = {src: [] for src, dst in tickets}

○

adj = {}

○

adj = defaultdict(list)

step 2· 그래프 구축 - 각 티켓을 간선으로 추가│ 중첩

○

adj[src].append(dst)

○

adj[dst].append(src)

○

adj[src] = [dst]

step 3· 사전식 순서를 위해 도착지 정렬│ 중첩

○

adj[key].sort()

○

adj[key].reverse()

○

# sorted는 인플레이스 작동하지 않으므로 정렬 생략

step 4· DFS 안전성 검사 - 출발지가 그래프에 있는지 확인│ 중첩

○

if src in adj:

○

if True:

○

while len(adj.get(src, [])) > 0:

step 5· 간선 제거 및 재귀 - 사용한 항공편 추적│ │ │ 중첩

○

adj[src].pop(0)

○

dfs(adj, dest)

○

adj[src].remove(dest); dfs(adj, dest)

step 6· 후위 순회 - 자식 방문 후 노드 추가│ 중첩

○

res.append(src)

○

res.insert(0, src)

○

res.append(src) # DFS 시작 시

step 7· 결과 역순 처리 - 후위 순회의 역순 보정

○

res.reverse()

○

res.sort()

○

pass # 역순이 맞는 답이라고 가정

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def findItinerary(self, tickets: List[List[str]]) -> List[str]:

        adj = {src: [] for src, dst in tickets}

        res = []

        for src, dst in tickets:

            adj[src].append(dst)

        for key in adj:

            adj[key].sort()

        def dfs(adj, src):

            if src in adj:

                destinations = adj[src][:]

                while destinations:

                    dest = destinations[0]

                    adj[src].pop(0)

                    dfs(adj, dest)

                    destinations = adj[src][:]

            res.append(src)

        dfs(adj, "JFK")

        res.reverse()

        if len(res) != len(tickets) + 1:

            return []

        return res

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

→

["JFK","MUC","LHR","SFO","SJC"]

case 2

[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

→

["JFK","ATL","JFK","SFO","ATL","SFO"]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.