[LeetCode] 332. Reconstruct Itinerary (Python)
- Reference
graph
- ๋ฐฑ์ค: List
- LeetCode: defaultdict(list)
Solution
import collections
from typing import List
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
answer = []
graph = collections.defaultdict(list)
for x, y in sorted(tickets):
graph[x].append(y)
def dfs(x: str):
# ์ฌ๊ท๋ก ๋ค ๋ฐฉ๋ฌธํ๋ค๋ ๋ป
while graph[x]:
# ์ดํ ์ ๋ฐฉ๋ฌธ -> ๊ฐ์ฅ ์ฒซ ๋ฒ์งธ ๊ฐ
dfs(graph[x].pop(0))
answer.append(x)
dfs('JFK')
answer.reverse()
return answer
Leave a comment