파이썬 알고리즘 인터뷰 - 38. 일정 재구성

 

<--- 리트코드 332. Reconstruct Itinerary --->

# 문제: [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다.

 

입력

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

출력

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

 

입력

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

출력

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

 

 

# 풀이

1. DFS로 일정 그래프 구성

import collections
 
def find_itinerary(tickets):
  graph = collections.defaultdict(list)
 
  for a, b in sorted(tickets):
    graph[a].append(b)
 
  route = []
 
  def dfs(a):
    while graph[a]:
      dfs(graph[a].pop(0))
    route.append(a)
 
  dfs('JFK')
  return route[::-1]
 
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
print(find_itinerary(tickets))

 

2. 스택 연산으로 큐 연산 최적화 시도

import collections
 
def find_itinerary(tickets):
  graph = collections.defaultdict(list)
 
  for a, b in sorted(tickets, reverse=True):
    graph[a].append(b)
 
  route = []
 
  def dfs(a):
    while graph[a]:
      dfs(graph[a].pop())
    route.append(a)
 
  dfs('JFK')
  return route[::-1]
 
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
print(find_itinerary(tickets))

 

3. 일정 그래프 반복

import collections
 
def find_itinerary(tickets):
  graph = collections.defaultdict(list)
 
  for a, b in sorted(tickets):
    graph[a].append(b)
 
  route, stack = [], ['JFK']
  while stack:
    while graph[stack[-1]]:
      stack.append(graph[stack[-1]].pop(0))
    route.append(stack.pop())
 
  return route[::-1]
 
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
print(find_itinerary(tickets))