Leetcode 332. Reconstruct Itinerary - Python

from LeetCode332

Leetcode 332 문제 보기

 

문제 이해하기

비행기 표 리스트 tickets가 주어졌다.

tickets의 각 원소는 하나의 표를 의미하며, [출발지, 도착지]로 구성된다.

JFK에서 출발하는 가능한 여행 경로 중, 사전순(lexical order)으로 방문하는 단 하나의 경로를 구하여라.

 

아이디어 구상

사전순으로 방문해야하므로, 리스트를 value로 하는 딕셔너리 형태로 그래프를 구성하되 각각의 key가 정렬된 value를 가지도록 하면 되겠다.

이후, 해당 그래프에서 JFK에서 시작하여 하나씩 value를 꺼내면 정답을 구할 수 있을 것이다.

 

이 때 약간의 트릭을 더 추가해 최적화를 해보자.

각각의 value들을 사전순으로 정렬하면, 값을 꺼낼 때 pop(0)로 해야한다. 그러나 이는 O(n)의 시간복잡도를 가진다.

만약 value들을 역사전순으로 정렬하면, 동일한 작업을 pop(), 즉 O(1)로 처리할 수 있을 것이다.

이렇게 역순으로 정렬한 value들을 가지는 그래프를 시각화해보면 다음과 같이 표현할 수 있다.

By Mesotes

 

이후로는 위 그래프에 대해 DFS를 수행하며 모든 경로를 탐색했을 경우 탐색을 종료하고 정답을 출력하도록 구현하면 되겠다.

 

풀이

우선 정답을 담을 리스트 res를 선언하고, 정렬된 리스트를 value로 하는 그래프를 구성해보자.

아이디어 구상에서 살펴봤듯이, 정렬은 역사전순으로 한다.

res = []
graph = collections.defaultdict(list)
for a, b in sorted(tickets, reverse=True):
    graph[a].append(b)

 

dfs()는 다음과 같다.

그래프의 key(출발지)에 대하여 value(도착지)들을 하나씩 출력한다.

while graph[a]:
    dfs(graph[a].pop())
res.append(a)

 

탐색을 종료하면 res에는 최종도착지부터 최초출발지까지 들어가있게 된다.

따라서 마지막 출력 시, 만들어진 res를 역순으로 출력한다.

 

전체 코드는 다음과 같다.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        res = []
        graph = collections.defaultdict(list)
        # initialize graph with sorted list as values
        for a, b in sorted(tickets, reverse=True):
            graph[a].append(b)
            
        
        def dfs(a):
            while graph[a]:
                dfs(graph[a].pop())
            res.append(a)
            
        dfs("JFK")
        return res[::-1]

 

---

Leetcode 332. Reconstruct Itinerary

https://leetcode.com/problems/reconstruct-itinerary/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다