38. Reconstruct Itinerary
🎯 leetcode - 332. Reconstruct Itinerary
🤔 私の答え
📌 質問する
- 파이썬 알고리즘 인터뷰 38번 문제
📌 名前の日付
2020.02.08
📌 試行回数
2 try / Failed
答えを間違える理由
😭 "여러 일정이 있는 경우 사전 어휘 순으로 방문한다"를 제대로 구현하지 못했다.
- input = [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]인 경우에 제대로 작동하지 않는다.
> 출력이 ['JFK', 'NRT', 'JFK', 'KUL'] 가 되어야 하는데
> 내것은 ['JFK', 'KUL']으로 잘못 출력된다.
😉 別の解釈
📌 一つ。再帰DFSによる解凍
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(list)
for start, last in sorted(tickets):
graph[start].append(last)
result = []
def dfs(route):
while graph[route]:
dfs(graph[route].pop(0))
result.append(route)
print(result)
dfs("JFK")
return result[::-1]
💡 トラブルシューティング方法
*key point : 백트래킹 되면서 result에 담는다!
→ 가장 나중에 방문할 장소부터 result에 담고, 마지막에 [::-1] 연산으로 경로를 뒤집는다.
- 참고로 defaultdict 안쓰면 에러가 생길 것이다.
따라서 조건 따로 안 걸거면 defaultdict를 꼭 쓰는 걸 추천~~
😾使用回归DFS的问题解决程序的目視😾
📌 二。繰り返し文で問題を解く
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = defaultdict(list)
for start, last in sorted(tickets):
graph[start].append(last)
result, stack = [], ["JFK"]
while stack:
while graph[stack[-1]]:
stack.append(graph[stack[-1]].pop(0))
result.append(stack.pop())
return result[::-1]
💡 トラブルシューティング方法
- 위의 재귀랑 원리는 같다.
- result는 위에랑 동일하게 경로를 "역순으로" 조회한 list이고
- stack은 그래프 조회 순서를 저장하기 위해 만든 스택이다.
만약 더이상 stack[-1] 뒤에 이어지는 추가적인 경로가 없다면 끝에서부터 차례대로 pop되면서 result에 담긴다.
----------------------------------------------------------------------------
⭐ 추가 설명 : stack이 왜 필요할까 ⭐
=> stack은 DFS에서 리프 노드까지 이동하는 과정을 차례대로 담은 것이다.
=> DFS 재귀에서는 백트래킹 되면서 차례대로 담기지만,
반복문에서는 추가적으로 경로를 담고 있는 스택을 생성해서 사용해야 한다.
=> 더 이상 stack[-1]의 요소에 대해 이어지는 경로가 없으면 pop()되어 result에 저장한다.
=> 다만 pop()하다가 만약 중간에 경로가 남아있는 요소가 있다면 다시 리프노드까지
이동하는 과정을 차례대로 stack에 담는다.
----------------------------------------------------------------------------
- 막히는 부분(더이상 경로 없는 경우)일 경우 while문을 돌지 않고 바로 result.append()로 넘어간다.
- 따라서 더이상 경로가 없기 때문에 stack에 담기지 않고 바로 result에 삽입된다.
😾用眼睛看重复文的解題过程😾
Reference
この問題について(38. Reconstruct Itinerary), 我々は、より多くの情報をここで見つけました https://velog.io/@eunseokim/38.-Reconstruct-Itineraryテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol