Python
파이썬 알고리즘 인터뷰 - 38. 일정 재구성
s코딩초보s
2022. 1. 30. 20:46
<--- 리트코드 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로 일정 그래프 구성
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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))
|
cs |
2. 스택 연산으로 큐 연산 최적화 시도
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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))
|
cs |
3. 일정 그래프 반복
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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))
|
cs |