[LeetCode] 332. Reconstruct Itinerary [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Reconstruct Itinerary - LeetCode>

1. 문제 (일정 재구성)

[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구하여라.

여러 일정이 있는 경우 사전 어휘 순으로 방문한다.

2. 풀이

DFS를 이용한 풀이

3. 코드

from collections import defaultdict
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:

        def dfs(city):
            while graph[city]:
                dfs(graph[city].pop(0))
            ret.append(city)

        ret = []
        graph = defaultdict(list)

        for a, b in sorted(tickets):
            graph[a].append(b)

        dfs("JFK")
        return ret[::-1]

• 결과 :

방식	Status	Runtime	Memory	Language
그래프 (DFS)	[Accepted]	80 ms	14.6 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋