문제
[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순으로 방문한다.
입력
[["MUC", "LHR"], ["JFK", "MUC"], ["SF0", "SJC"], ["LHR", "SF0"]]출력
["JFK", "MUC", "SF0", "SJC"]입력
[["JFK", "SF0"], ["JFK", "ATL"], ["SF0", "ATL"], ["ATL", "JFK"], ["ATL", "SF0"]]출력
["JFK", "ATL", "JFK", "SF0", "ATL", "SF0"]코드
DFS
from typing import List
import collections
class Solution:
def findItinerary(self, tickets: List[List[int]]) -> List[str]:
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]stack
from typing import List
import collections
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
for a, b in sorted(tickets):
graph[a].append(b)
route, stack = [], ['JFK']
while stack:
while graph[stack[-1]]:
# print(f'graph[stack[-1]: {graph[stack[-1]]}')
stack.append(graph[stack[-1]].pop(0))
# print(f'stack : {stack}')
# print(f'route : {route}')
route.append(stack.pop())
return route[::-1]풀이
DFS
여행 일정을 그래프로 구성하고 DFS로 풀이한다. 중복된 일정일 경우 어휘 순으로 방문하므로 그래프를 정렬해서 구성해야 한다.
graph = collections.defaultdict(list)
for a, b in sorted(tickets): # reverse=True가 정답 코드인 이유는 밑에..
graph[a].append(b)이제 그래프에서 하나씩 꺼낼 차례다. pop()으로 재귀 호출하면서 모두 꺼내 결과에 추가한다. 결과 리스트에는 역순으로 담기게 될 것이며, pop()으로 처리했기 때문에 드래프에서는 해당 경로는 사라지게 되어 재방문하게 되지는 않을 것이다. 여기서 중요한 점은 어휘순으로 방문해야 하기 때문에 pop(0)으로 첫 번째 값을 읽어야 한다.
def dfs(a):
while graph[a]:
dfs(graph[a].pop(0)) # pop()이 정답 코드인 이유는 밑에..
route.append(a)파이썬의 리스트의 경우 파라미터를 지정하지 않은 값, 그러니까 마지막 값을 꺼내는 pop()은 O(1)이지만, 첫 번째 값을 꺼내는 pop(0)은 O(n)이다. 따라서 좀 더 효율적인 구현을 위해서는 pop()으로, 즉 스택의 연산으로 처리될 수 있도록 개선이 필요하다.
for a, b in sorted(tickets, reverse=True):
graph[a].append(b)
...
def dfs(a):
while graph[a]:
dfs(graph[a].pop())
route.append(a)애당초 그래프를 역순으로 구성하면 추출 시에는 pop()으로 처리가 가능하다. 이렇게 하면 추출 시 시간 복잡도를 O(1)로 개선할 수 있다.
stack
동일한 형태로 그래프를 구성하되, 끄집어 낼 때 재귀가 아닌 스택을 이용한 반복으로 처리한다.
graph = collections.defaultdict(list)
for a, b in sorted(tickets):
graph[a].append(b)
...
stack = []
while stack:
while graph[stack[-1]]:
stack.append(graph[stack[-1]].pop(0))
...위 형태의 초기코드는 이해하기 쉽다. 밑에 헷갈렸던 부분에 이어서..
헷갈렸던 부분
stack
맨 위의 예제 2개는 끊어지는 경우가 없기 때문에 스택에 모든 경로가 한 번에 담긴다. 그런데 만약 경로가 끊어지는 경우가 있다면 스택에 모든 경로가 한 번에 담길 수 없다. 예를 들어 입력값이 [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]라면 그래프는 다음과 같은 형태가 된다.
defaultdict(list, {'JFK': ['KUL', 'NRT'], 'NRT': ['JFK']})이 경우 JFK → KUL에서 더 이상 진행할 수 없게 된다. 따라서 스택의 값을 다시 pop()하여 다음이 진행될 수 있게끔 해줘야 한다.
route, stack = [], ['JFK']
while stack:
while graph[stack[-1]]:
stack.append(graph[stack[-1]].pop(0))
route.append(stack.pop())DFS 재귀 호출과 달리 반복으로 풀이하려면 이처럼 한 번 더 풀어낼 수 있는 변수가 필요하다. 여기서는 최종 결과가 되는 변수이므로 DFS 재귀 풀이와 동일한 route로 변수명을 정했고, 여기에 스택을 pop()하여 담게 했다. 즉 경로가 풀리면서 거꾸로 담기게 될것이다. 따라서 최종 결과는 다시 뒤집어야 한다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]